/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/* All Rights Reserved */


#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/param.h>
#include <pkgdev.h>
#include <pkgstrct.h>
#include <locale.h>
#include <libintl.h>
#include <pkglib.h>
#include <libadm.h>
#include <libinst.h>

extern struct pkgdev pkgdev;

#define	MALSIZ	500
#define	EFACTOR	128ULL	/* typical size of a single entry in a pkgmap file */

#define	WRN_LIMIT	"WARNING: -l limit (%llu blocks) exceeds device " \
			"capacity (%llu blocks)"
#define	ERR_MEMORY	"memory allocation failure, errno=%d"
#define	ERR_TOOBIG	"%s (%llu blocks) does not fit on a volume"
#define	ERR_INFOFIRST	"information file <%s> must appear on first part"
#define	ERR_INFOSPACE	"all install files must appear on first part"
#define	ERR_VOLBLKS	"Objects selected for part %d require %llu blocks, " \
			"limit=%llu."
#define	ERR_VOLFILES	"Objects selected for part %d require %llu files, " \
			"limit=%llu."
#define	ERR_FREE	"package does not fit space currently available in <%s>"

struct data {
	fsblkcnt_t	blks;
	struct cfent *ept;
};

struct class_type {
	char *name;
	int first;
	int last;
};

static fsblkcnt_t	btotal;	/* blocks stored on current part */
static fsblkcnt_t	bmax;	/* maximum number of blocks on any part */

static fsfilcnt_t	ftotal;	/* files stored on current part */
static fsfilcnt_t	fmax;	/* maximum number of files on any part */
static fsblkcnt_t	bpkginfo;	/* blocks used by pkginfo file */
static char	**dirlist;
static short	volno;		/* current part */
static int	nparts = -1;	/* total number of parts */
static int	nclass;
static fsblkcnt_t	DIRSIZE;
static struct	class_type *cl;

static int	nodecount(char *path);
static int	store(struct data **, unsigned int, char *, fsblkcnt_t,
    fsblkcnt_t);
static void	addclass(char *aclass, int vol);
static void	allocnode(char *path);
static void	newvolume(struct data **, unsigned int, fsblkcnt_t limit,
    fsblkcnt_t);
static void	sortsize(struct data *f, struct data **sf, unsigned int eptnum);

int
splpkgmap(struct cfent **eptlist, unsigned int eptnum, char *order[],
    ulong_t bsize, ulong_t frsize, fsblkcnt_t *plimit, fsfilcnt_t *pilimit,
    fsblkcnt_t *pllimit)
{
	struct data	*f, **sf;
	struct cfent	*ept;
	register int	i, j;
	int		new_vol_set;
	short		new_vol;
	int		flag, errflg;
	fsblkcnt_t	total;
	fsblkcnt_t	btemp;
	fsfilcnt_t	ftemp;

	f = (struct data *)calloc(eptnum, sizeof (struct data));
	if (f == NULL) {
		progerr(gettext(ERR_MEMORY), errno);
		quit(99);
	}

	sf = (struct data **)calloc(eptnum, sizeof (struct data *));
	if (sf == NULL) {
		progerr(gettext(ERR_MEMORY), errno);
		quit(99);
	}

	nclass = 0;
	cl = (struct class_type *)calloc(MALSIZ, sizeof (struct class_type));
	if (cl == NULL) {
		progerr(gettext(ERR_MEMORY), errno);
		quit(99);
	}

	errflg = 0;

	/*
	 * The next bit of code checks to see if, when creating a package
	 * on a directory, there are enough free blocks and inodes before
	 * continuing.
	 */
	total = 0;
	/*
	 * DIRSIZE takes up 1 logical block, iff we have no frags, else
	 * it just takes a frag
	 */
	DIRSIZE = ((fsblkcnt_t)frsize > 0) ?
	    howmany(frsize, DEV_BSIZE) :
	    howmany(bsize, DEV_BSIZE);

	if (!pkgdev.mount) {
		allocnode(NULL);
		/*
		 * If we appear to have a valid value for free inodes
		 * and there's not enough for the package contents,
		 * then exit
		 */
		if ((*pilimit > 0) && (eptnum+1 > *pilimit)) {
			progerr(gettext(ERR_FREE), pkgdev.dirname);
			quit(1);
		}
		for (i = 0; i < eptnum; i++) {
			if (strchr("dxslcbp", eptlist[i]->ftype))
				continue;
			else {
				total +=
				    (nodecount(eptlist[i]->path) * DIRSIZE);
				total +=
				    nblk(eptlist[i]->cinfo.size, bsize, frsize);
				if (total > *plimit) {
					progerr(gettext(ERR_FREE),
					    pkgdev.dirname);
					quit(1);
				}
				allocnode(eptlist[i]->path);
			}
		}
	}
	/*
	 * if there is a value in pllimit (-l specified limit), use that for
	 * the limit from now on.
	 */

	if (*pllimit != 0) {
		if (pkgdev.mount && *pllimit > *plimit)
			logerr(gettext(WRN_LIMIT), *pllimit, *plimit);
		*plimit = *pllimit;
	}
	/*
	 * calculate number of physical blocks used by each object
	 */
	for (i = 0; i < eptnum; i++) {
		f[i].ept = ept = eptlist[i];
		if (ept->volno > nparts)
			nparts = ept->volno;
		addclass(ept->pkg_class, 0);
		if (strchr("dxslcbp", ept->ftype))
			/*
			 * virtual object (no contents)
			 */
			f[i].blks = 0;
		else
			/*
			 * space consumers
			 *
			 * (directories are space consumers as well, but they
			 * get accounted for later).
			 *
			 */

			f[i].blks = nblk(ept->cinfo.size, bsize, frsize);

		if (!bpkginfo && (strcmp(f[i].ept->path, "pkginfo") == 0))
			bpkginfo = f[i].blks;
	}

	/*
	 * Make sure that items slated for a given 'part' do not exceed a single
	 * volume.
	 */
	for (i = 1; i <= nparts; i++) {
		btemp = (bpkginfo + 2LL);
		ftemp = 2LL;
		if (i == 1) {
			/*
			 * save room for install directory
			 */
			ftemp += 2;
			btemp += nblk(eptnum * EFACTOR, bsize, frsize);
			btemp += 2;
		}
		allocnode(NULL);
		for (j = 0; j < eptnum; j++) {
			if (i == 1 && f[j].ept->ftype == 'i' &&
			    (strcmp(f[j].ept->path, "pkginfo") == 0 ||
			    strcmp(f[j].ept->path, "pkgmap") == 0))
				continue;
			if (f[j].ept->volno == i ||
			    (f[j].ept->ftype == 'i' && i == 1)) {
				ftemp += nodecount(f[j].ept->path);
				btemp += f[j].blks;
				allocnode(f[j].ept->path);
			}
		}
		btemp += (ftemp * DIRSIZE);
		if (btemp > *plimit) {
			progerr(gettext(ERR_VOLBLKS), i, btemp, *plimit);
			errflg++;
		/* If we have a valid inode limit, ensure this part will fit */
		} else if ((*pilimit > 0) && (ftemp+1 > *pilimit)) {
			progerr(gettext(ERR_VOLFILES), i, ftemp + 1, *pilimit);
			errflg++;
		}
	}
	if (errflg)
		quit(1);

	/*
	 * "sf" - array sorted in decreasing file size order, based on "f".
	 */
	sortsize(f, sf, eptnum);

	/*
	 * initialize first volume
	 */
	newvolume(sf, eptnum, *plimit, *pilimit);

	/*
	 * reserve room on first volume for pkgmap
	 */
	btotal += nblk((fsblkcnt_t)(eptnum * EFACTOR), bsize, frsize);
	ftotal++;


	/*
	 * initialize directory info
	 */
	allocnode(NULL);

	/*
	 * place installation files on first volume!
	 */
	flag = 0;
	for (j = 0; j < eptnum; ++j) {
		if (f[j].ept->ftype != 'i')
			continue;
		else if (!flag++) {
			/*
			 * save room for install directory
			 */
			ftotal++;
			btotal += 2ULL;
		}
		if (!f[j].ept->volno) {
			f[j].ept->volno = 1;
			ftotal++;
			btotal += f[j].blks;
		} else if (f[j].ept->volno != 1) {
			progerr(gettext(ERR_INFOFIRST), f[j].ept->path);
			errflg++;
		}
	}

	if (errflg)
		quit(1);
	if (btotal > *plimit) {
		progerr(gettext(ERR_INFOSPACE));
		quit(1);
	}

	/*
	 * Make sure that any given file will fit on a single volume, this
	 * calculation has to take into account packaging overhead, otherwise
	 * the function store() will go into a severe recursive plunge.
	 */
	for (j = 0; j < eptnum; ++j) {
		/*
		 * directory overhead.
		 */
		btemp = nodecount(f[j].ept->path) * DIRSIZE;
		/*
		 * packaging overhead.
		 */
		btemp += (bpkginfo + 2L);	/* from newvolume() */
		if ((f[j].blks + btemp) > *plimit) {
			errflg++;
			progerr(gettext(ERR_TOOBIG), f[j].ept->path, f[j].blks);
		}
	}
	if (errflg)
		quit(1);

	/*
	 * place classes listed on command line
	 */
	if (order) {
		for (i = 0; order[i]; ++i)  {
			while (store(sf, eptnum, order[i], *plimit, *pilimit))
				/* stay in loop until store is complete */
				/* void */;
		}
	}

	while (store(sf, eptnum, (char *)0, *plimit, *pilimit))
		/* stay in loop until store is complete */
		/* void */;

	/*
	 * place all virtual objects, e.g. links and spec devices
	 */
	for (i = 0; i < nclass; ++i) {
		/*
		 * if no objects were associated, attempt to
		 * distribute in order of class list
		 */
		if (cl[i].first == 0)
			cl[i].last = cl[i].first = (i ? cl[i-1].last : 1);
		for (j = 0; j < eptnum; j++) {
			if ((f[j].ept->volno == 0) &&
			    strcmp(f[j].ept->pkg_class, cl[i].name) == 0) {
				if (strchr("sl", f[j].ept->ftype))
					f[j].ept->volno = cl[i].last;
				else
					f[j].ept->volno = cl[i].first;
			}
		}
	}

	if (btotal)
		newvolume(sf, eptnum, *plimit, *pilimit);

	if (nparts > (volno - 1)) {
		new_vol = volno;
		for (i = volno; i <= nparts; i++) {
			new_vol_set = 0;
			for (j = 0; j < eptnum; j++) {
				if (f[j].ept->volno == i) {
					f[j].ept->volno = new_vol;
					new_vol_set = 1;
				}
			}
			new_vol += new_vol_set;
		}
		nparts = new_vol - 1;
	} else
		nparts = volno - 1;

	*plimit = bmax;
	*pilimit = fmax;

	/*
	 * free up dynamic space used by this module
	 */
	free(f);
	free(sf);
	for (i = 0; i < nclass; ++i)
		free(cl[i].name);
	free(cl);
	for (i = 0; dirlist[i]; i++)
		free(dirlist[i]);
	free(dirlist);

	return (errflg ? -1 : nparts);
}

static int
store(struct data **sf, unsigned int eptnum, char *aclass, fsblkcnt_t limit,
    fsfilcnt_t ilimit)
{
	int	i, svnodes, choice, select;
	long	ftemp;
	fsblkcnt_t	btemp;

	svnodes = 0;
	select = 0;
	choice = (-1);
	for (i = 0; i < eptnum; ++i) {
		if (sf[i]->ept->volno || strchr("sldxcbp", sf[i]->ept->ftype))
			continue; /* defer storage until class is selected */
		if (aclass && strcmp(aclass, sf[i]->ept->pkg_class))
			continue;
		select++; /* we need to place at least one object */
		ftemp = nodecount(sf[i]->ept->path);
		btemp = sf[i]->blks + (ftemp * DIRSIZE);
		if (((limit == 0) || ((btotal + btemp) <= limit)) &&
		    ((ilimit == 0) || ((ftotal + ftemp) < ilimit))) {
			/* largest object which fits on this volume */
			choice = i;
			svnodes = ftemp;
			break;
		}
	}
	if (!select)
		return (0); /* no more to objects to place */

	if (choice < 0) {
		newvolume(sf, eptnum, limit, ilimit);
		return (store(sf, eptnum, aclass, limit, ilimit));
	}
	sf[choice]->ept->volno = (char)volno;
	ftotal += svnodes + 1;
	btotal += sf[choice]->blks + (svnodes * DIRSIZE);
	allocnode(sf[i]->ept->path);
	addclass(sf[choice]->ept->pkg_class, volno);
	return (++choice); /* return non-zero if more work to do */
}

static void
allocnode(char *path)
{
	register int i;
	int	found;
	char	*pt;

	if (path == NULL) {
		if (dirlist) {
			/*
			 * free everything
			 */
			for (i = 0; dirlist[i]; i++)
				free(dirlist[i]);
			free(dirlist);
		}
		dirlist = (char **)calloc(MALSIZ, sizeof (char *));
		if (dirlist == NULL) {
			progerr(gettext(ERR_MEMORY), errno);
			quit(99);
		}
		return;
	}

	pt = path;
	if (*pt == '/')
		pt++;
	/*
	 * since the pathname supplied is never just a directory,
	 * we store only the dirname of of the path.
	 */
	while (pt = strchr(pt, '/')) {
		*pt = '\0';
		found = 0;
		for (i = 0; dirlist[i] != NULL; i++) {
			if (strcmp(path, dirlist[i]) == 0) {
				found++;
				break;
			}
		}
		if (!found) {
			/* insert this path in node list */
			dirlist[i] = qstrdup(path);
			if ((++i % MALSIZ) == 0) {
				dirlist = (char **)realloc(dirlist,
				    (i+MALSIZ) * sizeof (char *));
				if (dirlist == NULL) {
					progerr(gettext(ERR_MEMORY), errno);
					quit(99);
				}
			}
			dirlist[i] = (char *)NULL;
		}
		*pt++ = '/';
	}
}

static int
nodecount(char *path)
{
	char	*pt;
	int	i, found, count;

	pt = path;
	if (*pt == '/')
		pt++;

	/*
	 * we want to count the number of path
	 * segments that need to be created, not
	 * including the basename of the path;
	 * this works only since we are never
	 * passed a pathname which itself is a
	 * directory
	 */
	count = 0;
	while (pt = strchr(pt, '/')) {
		*pt = '\0';
		found = 0;
		for (i = 0; dirlist[i]; i++) {
			if (strcmp(path, dirlist[i]) != 0) {
				found++;
				break;
			}
		}
		if (!found)
			count++;
		*pt++ = '/';
	}
	return (count);
}

static void
newvolume(struct data **sf, unsigned int eptnum, fsblkcnt_t limit,
    fsblkcnt_t ilimit)
{
	register int i;
	int	newnodes;

	if (volno) {
		(void) fprintf(stderr,
		    gettext("part %2d -- %llu blocks, %llu entries\n"),
		    volno, btotal, ftotal);
		if (btotal > bmax)
			bmax = btotal;
		if (ftotal > fmax)
			fmax = ftotal;
		btotal = bpkginfo + 2ULL;
		ftotal = 2;
	} else {
		btotal = 2ULL;
		ftotal = 1;
	}
	volno++;

	/*
	 * zero out directory storage
	 */
	allocnode((char *)0);

	/*
	 * force storage of files whose volume number has already been assigned
	 */
	for (i = 0; i < eptnum; i++) {
		if (sf[i]->ept->volno == volno) {
			newnodes = nodecount(sf[i]->ept->path);
			ftotal += newnodes + 1;
			btotal += sf[i]->blks + (newnodes * DIRSIZE);
			if (btotal > limit) {
				progerr(gettext(ERR_VOLBLKS), volno, btotal,
				    limit);
				quit(1);
			} else if ((ilimit == 0) && (ftotal+1 > ilimit)) {
				progerr(gettext(ERR_VOLFILES), volno, ftotal+1,
				    ilimit);
				quit(1);
			}
		}
	}
}

static void
addclass(char *aclass, int vol)
{
	int i;

	for (i = 0; i < nclass; ++i) {
		if (strcmp(cl[i].name, aclass) == 0) {
			if (vol <= 0)
				return;
			if (!cl[i].first || (vol < cl[i].first))
				cl[i].first = vol;
			if (vol > cl[i].last)
				cl[i].last = vol;
			return;
		}
	}
	cl[nclass].name = qstrdup(aclass);
	cl[nclass].first = vol;
	cl[nclass].last = vol;
	if ((++nclass % MALSIZ) == 0) {
		cl = (struct class_type *)realloc((char *)cl,
		    sizeof (struct class_type) * (nclass+MALSIZ));
		if (!cl) {
			progerr(gettext(ERR_MEMORY), errno);
			quit(99);
		}
	}
}

static void
sortsize(struct data *f, struct data **sf, unsigned int eptnum)
{
	int	nsf;
	int	j, k;
	unsigned int	i;

	nsf = 0;
	for (i = 0; i < eptnum; i++) {
		for (j = 0; j < nsf; ++j) {
			if (f[i].blks > sf[j]->blks) {
				for (k = nsf; k > j; k--) {
					sf[k] = sf[k-1];
				}
				break;
			}
		}
		sf[j] = &f[i];
		nsf++;
	}
}