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
pack(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
packdevi(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
sameas(struct devi * i1,struct devi * i2)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
addparents(struct devi * src,struct devi * dst)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
nparents(struct devi ** p,struct devbase * dev,int unit)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
packlocs(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
packpvec(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
findvec(const void * ptr,int hash,int len,vec_cmp_func cmp,int nextplace)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
samelocs(const void * ptr,int off,int len)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
addlocs(const char ** locs,int len)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
loclencmp(const void * a,const void * b)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
samepv(const void * ptr,int off,int len)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
addpv(short * pv,int len)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
pvlencmp(const void * a,const void * b)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
resettails(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 }
504