GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/config/pack.c Lines: 0 164 0.0 %
Date: 2017-11-13 Branches: 0 114 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: pack.c,v 1.18 2015/01/16 06:40:16 deraadt Exp $	*/
2
/*	$NetBSD: pack.c,v 1.5 1996/08/31 21:15:11 mycroft Exp $	*/
3
4
/*
5
 * Copyright (c) 1992, 1993
6
 *	The Regents of the University of California.  All rights reserved.
7
 *
8
 * This software was developed by the Computer Systems Engineering group
9
 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
10
 * contributed to Berkeley.
11
 *
12
 * All advertising materials mentioning features or use of this software
13
 * must display the following acknowledgement:
14
 *	This product includes software developed by the University of
15
 *	California, Lawrence Berkeley Laboratories.
16
 *
17
 * Redistribution and use in source and binary forms, with or without
18
 * modification, are permitted provided that the following conditions
19
 * are met:
20
 * 1. Redistributions of source code must retain the above copyright
21
 *    notice, this list of conditions and the following disclaimer.
22
 * 2. Redistributions in binary form must reproduce the above copyright
23
 *    notice, this list of conditions and the following disclaimer in the
24
 *    documentation and/or other materials provided with the distribution.
25
 * 3. Neither the name of the University nor the names of its contributors
26
 *    may be used to endorse or promote products derived from this software
27
 *    without specific prior written permission.
28
 *
29
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39
 * SUCH DAMAGE.
40
 *
41
 *	from: @(#)pack.c	8.1 (Berkeley) 6/6/93
42
 */
43
44
#include <stdlib.h>
45
#include <string.h>
46
47
#include "config.h"
48
49
/*
50
 * Packing.  We have three separate kinds of packing here.
51
 *
52
 * First, we pack device instances, to collapse things like
53
 *
54
 *	uba0 at sbi0 nexus ?
55
 *	uba0 at bi0 nexus ?
56
 *
57
 * into a single instance that is "at sbi0 or bi0".
58
 *
59
 * Second, we pack locators.  Given something like
60
 *
61
 *	hp0 at mba0 drive 0
62
 *	hp* at mba* drive ?
63
 *	ht0 at mba0 drive 0
64
 *	tu0 at ht0 slave 0
65
 *	ht* at mba* drive ?
66
 *	tu* at ht* slave ?
67
 *
68
 * (where the default drive and slave numbers are -1), we have three
69
 * locators whose value is 0 and three whose value is -1.  Rather than
70
 * emitting six integers, we emit just two.
71
 *
72
 * Finally, we pack parent vectors.  This is very much like packing
73
 * locators.  Unlike locators, however, parent vectors are always
74
 * terminated by -1 (rather like the way C strings always end with
75
 * a NUL).
76
 *
77
 * When packing locators, we would like to find sequences such as
78
 *	{1 2 3} {2 3 4} {3} {4 5}
79
 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
80
 * given by the appropriate offset (here 0, 1, 2, and 3 respectively).
81
 * When we pack parent vectors, overlap of this sort is impossible.
82
 * Non-overlapping packing is much easier, and so we use that here
83
 * and miss out on the chance to squeeze the locator sequence optimally.
84
 * (So it goes.)
85
 */
86
87
typedef int (*vec_cmp_func)(const void *, int, int);
88
89
#define	TAILHSIZE	128
90
#define	PVHASH(i)	((i) & (TAILHSIZE - 1))
91
#define	LOCHASH(l)	(((long)(l) >> 2) & (TAILHSIZE - 1))
92
struct tails {
93
	struct	tails *t_next;
94
	int	t_ends_at;
95
};
96
97
static struct tails *tails[TAILHSIZE];
98
static int locspace;
99
static int pvecspace;
100
static int longest_pvec;
101
102
static void packdevi(void);
103
static void packlocs(void);
104
static void packpvec(void);
105
106
static void addparents(struct devi *src, struct devi *dst);
107
static int nparents(struct devi **, struct devbase *, int);
108
static int sameas(struct devi *, struct devi *);
109
static int findvec(const void *, int, int, vec_cmp_func, int);
110
static int samelocs(const void *, int, int);
111
static int addlocs(const char **, int);
112
static int loclencmp(const void *, const void *);
113
static int samepv(const void *, int, int);
114
static int addpv(short *, int);
115
static int pvlencmp(const void *, const void *);
116
static void resettails(void);
117
118
void
119
pack(void)
120
{
121
	struct devi *i;
122
	int n;
123
124
	/* Pack instances and make parent vectors. */
125
	packdevi();
126
127
	/*
128
	 * Now that we know what we have, find upper limits on space
129
	 * needed for the loc[] and pv[] tables, and find the longest
130
	 * single pvec.  The loc and pv table sizes are bounded by
131
	 * what we would get if no packing occurred.
132
	 */
133
	locspace = pvecspace = 0;
134
	for (i = alldevi; i != NULL; i = i->i_next) {
135
		if (i->i_collapsed)
136
			continue;
137
		locspace += i->i_atattr->a_loclen;
138
		n = i->i_pvlen + 1;
139
		if (n > longest_pvec)
140
			longest_pvec = n;
141
		pvecspace += n;
142
	}
143
144
	/* Allocate and pack loc[]. */
145
	locators.vec = ereallocarray(NULL, locspace, sizeof(*locators.vec));
146
	locators.used = 0;
147
	packlocs();
148
149
	/* Allocate and pack pv[]. */
150
	parents.vec = ereallocarray(NULL, pvecspace, sizeof(*parents.vec));
151
	parents.used = 0;
152
	packpvec();
153
}
154
155
/*
156
 * Pack instances together wherever possible.  When everything is
157
 * packed, go back and set up the parents for each.  We must do this
158
 * on a second pass because during the first one, we do not know which,
159
 * if any, of the parents will collapse during packing.
160
 */
161
void
162
packdevi(void)
163
{
164
	struct devi *i, *l, *p;
165
	struct deva *d;
166
	int j, m, n;
167
168
	packed = ereallocarray(NULL, ndevi + 1, sizeof *packed);
169
	n = 0;
170
	for (d = alldevas; d != NULL; d = d->d_next) {
171
		/*
172
		 * For each instance of each attachment, add or collapse
173
		 * all its aliases.
174
		 */
175
		for (i = d->d_ihead; i != NULL; i = i->i_asame) {
176
			m = n;
177
			for (l = i; l != NULL; l = l->i_alias) {
178
				/* Skip if we already handled this one.  */
179
				if (l->i_cfindex >= 0)
180
					continue;
181
				l->i_pvlen = 0;
182
				l->i_pvoff = -1;
183
				l->i_locoff = -1;
184
				/* try to find an equivalent for l */
185
				for (j = m; j < n; j++) {
186
					p = packed[j];
187
					if (sameas(l, p)) {
188
						l->i_collapsed = 1;
189
						l->i_cfindex = p->i_cfindex;
190
						goto nextalias;
191
					}
192
				}
193
				/* could not find a suitable alias */
194
				l->i_collapsed = 0;
195
				l->i_cfindex = n;
196
				l->i_parents = emalloc(sizeof(*l->i_parents));
197
				l->i_parents[0] = NULL;
198
				packed[n++] = l;
199
			nextalias:;
200
			}
201
		}
202
	}
203
	npacked = n;
204
	packed[n] = NULL;
205
	for (i = alldevi; i != NULL; i = i->i_next)
206
		addparents(i, packed[i->i_cfindex]);
207
}
208
209
/*
210
 * Return true if two aliases are "the same".  In this case, they need
211
 * to attach via the same attribute, have the same config flags, and
212
 * have the same locators.
213
 */
214
static int
215
sameas(struct devi *i1, struct devi *i2)
216
{
217
	const char **p1, **p2;
218
219
	if (i1->i_atattr != i2->i_atattr)
220
		return (0);
221
	if (i1->i_cfflags != i2->i_cfflags)
222
		return (0);
223
	for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++)
224
		if (*p1++ == 0)
225
			return (1);
226
	return 0;
227
}
228
229
/*
230
 * Add the parents associated with "src" to the (presumably uncollapsed)
231
 * instance "dst".
232
 */
233
static void
234
addparents(struct devi *src, struct devi *dst)
235
{
236
	struct nvlist *nv;
237
	struct devi *i, **p, **q;
238
	int j, n, old, new, ndup;
239
240
	if (dst->i_collapsed)
241
		panic("addparents() i_collapsed");
242
243
	/* Collect up list of parents to add. */
244
	if (src->i_at == NULL)	/* none, because we are "at root" */
245
		return;
246
	if (src->i_atdev != NULL) {
247
		n = nparents(NULL, src->i_atdev, src->i_atunit);
248
		p = ereallocarray(NULL, n, sizeof *p);
249
		if (n == 0)
250
			return;
251
		(void)nparents(p, src->i_atdev, src->i_atunit);
252
	} else {
253
		n = 0;
254
		for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
255
			n += nparents(NULL, nv->nv_ptr, src->i_atunit);
256
		if (n == 0)
257
			return;
258
		p = ereallocarray(NULL, n, sizeof *p);
259
		n = 0;
260
		for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next)
261
			n += nparents(p + n, nv->nv_ptr, src->i_atunit);
262
	}
263
	/* Now elide duplicates. */
264
	ndup = 0;
265
	for (j = 0; j < n; j++) {
266
		i = p[j];
267
		for (q = dst->i_parents; *q != NULL; q++) {
268
			if (*q == i) {
269
				ndup++;
270
				p[j] = NULL;
271
				break;
272
			}
273
		}
274
	}
275
	/* Finally, add all the non-duplicates. */
276
	old = dst->i_pvlen;
277
	new = old + (n - ndup);
278
	if (old > new)
279
		panic("addparents() old > new");
280
	if (old == new) {
281
		free(p);
282
		return;
283
	}
284
	dst->i_parents = q = ereallocarray(dst->i_parents, new + 1, sizeof(*q));
285
	dst->i_pvlen = new;
286
	q[new] = NULL;
287
	q += old;
288
	for (j = 0; j < n; j++)
289
		if (p[j] != NULL)
290
			*q++ = p[j];
291
	free(p);
292
}
293
294
/*
295
 * Count up parents, and optionally store pointers to each.
296
 */
297
static int
298
nparents(struct devi **p, struct devbase *dev, int unit)
299
{
300
	struct devi *i, *l;
301
	int n;
302
303
	n = 0;
304
	/* for each instance ... */
305
	for (i = dev->d_ihead; i != NULL; i = i->i_bsame) {
306
		/* ... take each un-collapsed alias */
307
		for (l = i; l != NULL; l = l->i_alias) {
308
			if (!l->i_collapsed &&
309
			    (unit == WILD || unit == l->i_unit)) {
310
				if (p != NULL)
311
					*p++ = l;
312
				n++;
313
			}
314
		}
315
	}
316
	return (n);
317
}
318
319
static void
320
packlocs(void)
321
{
322
	struct devi **p, *i;
323
	int l, o;
324
325
	qsort(packed, npacked, sizeof *packed, loclencmp);
326
	for (p = packed; (i = *p) != NULL; p++) {
327
		if ((l = i->i_atattr->a_loclen) > 0) {
328
			o = findvec(i->i_locs, LOCHASH(i->i_locs[l - 1]), l,
329
				    samelocs, locators.used);
330
			i->i_locoff = o < 0 ? addlocs(i->i_locs, l) : o;
331
		} else
332
			i->i_locoff = -1;
333
	}
334
	resettails();
335
}
336
337
static void
338
packpvec(void)
339
{
340
	struct devi **p, *i, **par;
341
	int l, v, o;
342
	short *vec;
343
344
	vec = ereallocarray(NULL, longest_pvec, sizeof(*vec));
345
	qsort(packed, npacked, sizeof *packed, pvlencmp);
346
	for (p = packed; (i = *p) != NULL; p++) {
347
		l = i->i_pvlen;
348
		if (l > longest_pvec)
349
			panic("packpvec");
350
		par = i->i_parents;
351
		for (v = 0; v < l; v++)
352
			vec[v] = par[v]->i_cfindex;
353
		if (l == 0 || (o = findvec(vec, PVHASH(vec[l - 1]), l,
354
		    samepv, parents.used)) < 0)
355
			o = addpv(vec, l);
356
		i->i_pvoff = o;
357
	}
358
	free(vec);
359
	resettails();
360
}
361
362
/*
363
 * Return the index at which the given vector already exists, or -1
364
 * if it is not anywhere in the current set.  If we return -1, we assume
365
 * our caller will add it at the end of the current set, and we make
366
 * sure that next time, we will find it there.
367
 */
368
static int
369
findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
370
{
371
	struct tails *t, **hp;
372
	int off;
373
374
	hp = &tails[hash];
375
	for (t = *hp; t != NULL; t = t->t_next) {
376
		off = t->t_ends_at - len;
377
		if (off >= 0 && (*cmp)(ptr, off, len))
378
			return (off);
379
	}
380
	t = emalloc(sizeof(*t));
381
	t->t_next = *hp;
382
	*hp = t;
383
	t->t_ends_at = nextplace + len;
384
	return (-1);
385
}
386
387
/*
388
 * Comparison function for locators.
389
 */
390
static int
391
samelocs(const void *ptr, int off, int len)
392
{
393
	const char **p, **q;
394
395
	for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;)
396
		if (*p++ != *q++)
397
			return (0);	/* different */
398
	return (1);			/* same */
399
}
400
401
/*
402
 * Add the given locators at the end of the global loc[] table.
403
 */
404
static int
405
addlocs(const char **locs, int len)
406
{
407
	const char **p;
408
	int ret;
409
410
	ret = locators.used;
411
	if ((locators.used = ret + len) > locspace)
412
		panic("addlocs: overrun");
413
	for (p = &locators.vec[ret]; --len >= 0;)
414
		*p++ = *locs++;
415
	return (ret);
416
}
417
418
/*
419
 * Comparison function for qsort-by-locator-length, longest first.
420
 * We rashly assume that subtraction of these lengths does not overflow.
421
 */
422
static int
423
loclencmp(const void *a, const void *b)
424
{
425
	int l1, l2;
426
427
	l1 = (*(struct devi **)a)->i_atattr->a_loclen;
428
	l2 = (*(struct devi **)b)->i_atattr->a_loclen;
429
	return (l2 - l1);
430
}
431
432
/*
433
 * Comparison function for parent vectors.
434
 */
435
static int
436
samepv(const void *ptr, int off, int len)
437
{
438
	short *p, *q;
439
440
	for (p = &parents.vec[off], q = (short *)ptr; --len >= 0;)
441
		if (*p++ != *q++)
442
			return (0);	/* different */
443
	return (1);			/* same */
444
}
445
446
/*
447
 * Add the given parent vectors at the end of the global pv[] table.
448
 */
449
static int
450
addpv(short *pv, int len)
451
{
452
	short *p;
453
	int ret;
454
	static int firstend = -1;
455
456
	/*
457
	 * If the vector is empty, reuse the first -1.  It will be
458
	 * there if there are any nonempty vectors at all, since we
459
	 * do the longest first.  If there are no nonempty vectors,
460
	 * something is probably wrong, but we will ignore that here.
461
	 */
462
	if (len == 0 && firstend >= 0)
463
		return (firstend);
464
	len++;			/* account for trailing -1 */
465
	ret = parents.used;
466
	if ((parents.used = ret + len) > pvecspace)
467
		panic("addpv: overrun");
468
	for (p = &parents.vec[ret]; --len > 0;)
469
		*p++ = *pv++;
470
	*p = -1;
471
	if (firstend < 0)
472
		firstend = parents.used - 1;
473
	return (ret);
474
}
475
476
/*
477
 * Comparison function for qsort-by-parent-vector-length, longest first.
478
 * We rashly assume that subtraction of these lengths does not overflow.
479
 */
480
static int
481
pvlencmp(const void *a, const void *b)
482
{
483
	int l1, l2;
484
485
	l1 = (*(struct devi **)a)->i_pvlen;
486
	l2 = (*(struct devi **)b)->i_pvlen;
487
	return (l2 - l1);
488
}
489
490
static void
491
resettails(void)
492
{
493
	struct tails **p, *t, *next;
494
	int i;
495
496
	for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
497
		for (t = *p; t != NULL; t = next) {
498
			next = t->t_next;
499
			free(t);
500
		}
501
		*p = NULL;
502
	}
503
}