1/*	$NetBSD: pack.c,v 1.7 2010/01/21 18:06:38 pooka Exp $	*/
2
3/*
4 * Copyright (c) 1992, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This software was developed by the Computer Systems Engineering group
8 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
9 * contributed to Berkeley.
10 *
11 * All advertising materials mentioning features or use of this software
12 * must display the following acknowledgement:
13 *	This product includes software developed by the University of
14 *	California, Lawrence Berkeley Laboratories.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 *    notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 *    notice, this list of conditions and the following disclaimer in the
23 *    documentation and/or other materials provided with the distribution.
24 * 3. Neither the name of the University nor the names of its contributors
25 *    may be used to endorse or promote products derived from this software
26 *    without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 *
40 *	from: @(#)pack.c	8.1 (Berkeley) 6/6/93
41 */
42
43#if HAVE_NBTOOL_CONFIG_H
44#include "nbtool_config.h"
45#endif
46
47#include <sys/param.h>
48#include <stdlib.h>
49#include <string.h>
50#include <util.h>
51#include "defs.h"
52
53/*
54 * Packing.  We have three separate kinds of packing here.
55 *
56 * First, we pack device instances which have identical parent specs.
57 *
58 * Second, we pack locators.  Given something like
59 *
60 *	hp0 at mba0 drive 0
61 *	hp* at mba* drive ?
62 *	ht0 at mba0 drive 0
63 *	tu0 at ht0 slave 0
64 *	ht* at mba* drive ?
65 *	tu* at ht* slave ?
66 *
67 * (where the default drive and slave numbers are -1), we have three
68 * locators whose value is 0 and three whose value is -1.  Rather than
69 * emitting six integers, we emit just two.
70 *
71 * When packing locators, we would like to find sequences such as
72 *	{1 2 3} {2 3 4} {3} {4 5}
73 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
74 * given by the appropriate offset (here 0, 1, 2, and 3 respectively).
75 * Non-overlapping packing is much easier, and so we use that here
76 * and miss out on the chance to squeeze the locator sequence optimally.
77 * (So it goes.)
78 */
79
80typedef int (*vec_cmp_func)(const void *, int, int);
81
82#define	TAILHSIZE	128
83#define	PVHASH(i)	((i) & (TAILHSIZE - 1))
84#define	LOCHASH(l)	(((long)(l) >> 2) & (TAILHSIZE - 1))
85struct tails {
86	struct	tails *t_next;
87	int	t_ends_at;
88};
89
90static struct tails *tails[TAILHSIZE];
91static int locspace;
92
93static void packdevi(void);
94static void packlocs(void);
95
96static int sameas(struct devi *, struct devi *);
97static int findvec(const void *, int, int, vec_cmp_func, int);
98static int samelocs(const void *, int, int);
99static int addlocs(const char **, int);
100static int loclencmp(const void *, const void *);
101static void resettails(void);
102
103void
104pack(void)
105{
106	struct pspec *p;
107	struct devi *i;
108
109	/* Pack instances and make parent vectors. */
110	packdevi();
111
112	/*
113	 * Now that we know what we have, find upper limits on space
114	 * needed for the loc[] table.  The loc table size is bounded by
115	 * what we would get if no packing occurred.
116	 */
117	locspace = 0;
118	TAILQ_FOREACH(i, &alldevi, i_next) {
119		if (!i->i_active == DEVI_ACTIVE || i->i_collapsed)
120			continue;
121		if ((p = i->i_pspec) == NULL)
122			continue;
123		locspace += p->p_iattr->a_loclen;
124	}
125
126	/* Allocate and pack loc[]. */
127	locators.vec = ecalloc((size_t)locspace, sizeof(*locators.vec));
128	locators.used = 0;
129	packlocs();
130}
131
132/*
133 * Pack device instances together wherever possible.
134 */
135static void
136packdevi(void)
137{
138	struct devi *firststar, *i, **ip, *l, *p;
139	struct devbase *d;
140	int j, m, n;
141
142	/*
143	 * Sort all the cloning units to after the non-cloning units,
144	 * preserving order of cloning and non-cloning units with
145	 * respect to other units of the same type.
146	 *
147	 * Algorithm: Walk down the list until the first cloning unit is
148	 * seen for the second time (or until the end of the list, if there
149	 * are no cloning units on the list), moving starred units to the
150	 * end of the list.
151	 */
152	TAILQ_FOREACH(d, &allbases, d_next) {
153		ip = &d->d_ihead;
154		firststar = NULL;
155
156		for (i = *ip; i != firststar; i = *ip) {
157			if (i->i_unit != STAR) {
158				/* try i->i_bsame next */
159				ip = &i->i_bsame;
160			} else {
161				if (firststar == NULL)
162					firststar = i;
163
164				*d->d_ipp = i;
165				d->d_ipp = &i->i_bsame;
166
167				*ip = i->i_bsame;
168				i->i_bsame = NULL;
169
170				/* leave ip alone; try (old) i->i_bsame next */
171			}
172		}
173	}
174
175	packed = ecalloc((size_t)ndevi + 1, sizeof *packed);
176	n = 0;
177	TAILQ_FOREACH(d, &allbases, d_next) {
178		/*
179		 * For each instance of each device, add or collapse
180		 * all its aliases.
181		 *
182		 * Pseudo-devices have a non-empty d_ihead for convenience.
183		 * Ignore them.
184		 */
185		if (d->d_ispseudo)
186			continue;
187		for (i = d->d_ihead; i != NULL; i = i->i_bsame) {
188			m = n;
189			for (l = i; l != NULL; l = l->i_alias) {
190				if (l->i_active != DEVI_ACTIVE
191				    || i->i_pseudoroot)
192					continue;
193				l->i_locoff = -1;
194				/* try to find an equivalent for l */
195				for (j = m; j < n; j++) {
196					p = packed[j];
197					if (sameas(l, p)) {
198						l->i_collapsed = 1;
199						l->i_cfindex = p->i_cfindex;
200						goto nextalias;
201					}
202				}
203				/* could not find a suitable alias */
204				l->i_collapsed = 0;
205				l->i_cfindex = n;
206				packed[n++] = l;
207 nextalias:;
208			}
209		}
210	}
211	npacked = n;
212	packed[n] = NULL;
213}
214
215/*
216 * Return true if two aliases are "the same".  In this case, they need
217 * to have the same parent spec, have the same config flags, and have
218 * the same locators.
219 */
220static int
221sameas(struct devi *i1, struct devi *i2)
222{
223	const char **p1, **p2;
224
225	if (i1->i_pspec != i2->i_pspec)
226		return (0);
227	if (i1->i_cfflags != i2->i_cfflags)
228		return (0);
229	for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++)
230		if (*p1++ == 0)
231			return (1);
232	return (0);
233}
234
235static void
236packlocs(void)
237{
238	struct pspec *ps;
239	struct devi **p, *i;
240	int l,o;
241	extern int Pflag;
242
243	qsort(packed, npacked, sizeof *packed, loclencmp);
244	for (p = packed; (i = *p) != NULL; p++) {
245		if ((ps = i->i_pspec) != NULL &&
246		    (l = ps->p_iattr->a_loclen) > 0) {
247			if (Pflag) {
248				o = findvec(i->i_locs,
249				    LOCHASH(i->i_locs[l - 1]), l,
250				    samelocs, locators.used);
251				i->i_locoff = o < 0 ?
252				    addlocs(i->i_locs, l) : o;
253			} else
254				i->i_locoff = addlocs(i->i_locs, l);
255		} else
256			i->i_locoff = -1;
257	}
258	resettails();
259}
260
261/*
262 * Return the index at which the given vector already exists, or -1
263 * if it is not anywhere in the current set.  If we return -1, we assume
264 * our caller will add it at the end of the current set, and we make
265 * sure that next time, we will find it there.
266 */
267static int
268findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
269{
270	struct tails *t, **hp;
271	int off;
272
273	hp = &tails[hash];
274	for (t = *hp; t != NULL; t = t->t_next) {
275		off = t->t_ends_at - len;
276		if (off >= 0 && (*cmp)(ptr, off, len))
277			return (off);
278	}
279	t = ecalloc(1, sizeof(*t));
280	t->t_next = *hp;
281	*hp = t;
282	t->t_ends_at = nextplace + len;
283	return (-1);
284}
285
286/*
287 * Comparison function for locators.
288 */
289static int
290samelocs(const void *ptr, int off, int len)
291{
292	const char * const *p, * const *q;
293
294	for (p = &locators.vec[off], q = (const char * const *)ptr; --len >= 0;)
295		if (*p++ != *q++)
296			return (0);	/* different */
297	return (1);			/* same */
298}
299
300/*
301 * Add the given locators at the end of the global loc[] table.
302 */
303static int
304addlocs(const char **locs, int len)
305{
306	const char **p;
307	int ret;
308
309	ret = locators.used;
310	if ((locators.used = ret + len) > locspace)
311		panic("addlocs: overrun");
312	for (p = &locators.vec[ret]; --len >= 0;)
313		*p++ = *locs++;
314	return (ret);
315}
316
317/*
318 * Comparison function for qsort-by-locator-length, longest first.
319 * We rashly assume that subtraction of these lengths does not overflow.
320 */
321static int
322loclencmp(const void *a, const void *b)
323{
324	const struct pspec *p1, *p2;
325	int l1, l2;
326
327	p1 = (*(const struct devi * const *)a)->i_pspec;
328	l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0;
329
330	p2 = (*(const struct devi * const *)b)->i_pspec;
331	l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0;
332
333	return (l2 - l1);
334}
335
336static void
337resettails(void)
338{
339	struct tails **p, *t, *next;
340	int i;
341
342	for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
343		for (t = *p; t != NULL; t = next) {
344			next = t->t_next;
345			free(t);
346		}
347		*p = NULL;
348	}
349}
350