1 /* $NetBSD: pack.c,v 1.12 2025/01/07 14:21:11 joe 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/cdefs.h>
48 __RCSID("$NetBSD: pack.c,v 1.12 2025/01/07 14:21:11 joe Exp $");
49
50 #include <sys/param.h>
51 #include <stdlib.h>
52 #include <string.h>
53 #include <util.h>
54 #include "defs.h"
55
56 /*
57 * Packing. We have three separate kinds of packing here.
58 *
59 * First, we pack device instances which have identical parent specs.
60 *
61 * Second, we pack locators. Given something like
62 *
63 * hp0 at mba0 drive 0
64 * hp* at mba* drive ?
65 * ht0 at mba0 drive 0
66 * tu0 at ht0 slave 0
67 * ht* at mba* drive ?
68 * tu* at ht* slave ?
69 *
70 * (where the default drive and slave numbers are -1), we have three
71 * locators whose value is 0 and three whose value is -1. Rather than
72 * emitting six integers, we emit just two.
73 *
74 * When packing locators, we would like to find sequences such as
75 * {1 2 3} {2 3 4} {3} {4 5}
76 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
77 * given by the appropriate offset (here 0, 1, 2, and 3 respectively).
78 * Non-overlapping packing is much easier, and so we use that here
79 * and miss out on the chance to squeeze the locator sequence optimally.
80 * (So it goes.)
81 */
82
83 typedef int (*vec_cmp_func)(const void *, int, int);
84
85 #define TAILHSIZE 128
86 #define PVHASH(i) ((i) & (TAILHSIZE - 1))
87 #define LOCHASH(l) (((long)(l) >> 2) & (TAILHSIZE - 1))
88 struct tails {
89 struct tails *t_next;
90 int t_ends_at;
91 };
92
93 static struct tails *tails[TAILHSIZE];
94 static int locspace;
95
96 static void packdevi(void);
97 static void packlocs(void);
98
99 static int sameas(struct devi *, struct devi *);
100 static int findvec(const void *, int, int, vec_cmp_func, int);
101 static int samelocs(const void *, int, int);
102 static int addlocs(const char **, int);
103 static int loclencmp(const void *, const void *);
104 static void resettails(void);
105
106 void
pack(void)107 pack(void)
108 {
109 struct pspec *p;
110 struct devi *i;
111
112 /* Pack instances and make parent vectors. */
113 packdevi();
114
115 /*
116 * Now that we know what we have, find upper limits on space
117 * needed for the loc[] table. The loc table size is bounded by
118 * what we would get if no packing occurred.
119 */
120 locspace = 0;
121 TAILQ_FOREACH(i, &alldevi, i_next) {
122 if (i->i_active != DEVI_ACTIVE || i->i_collapsed)
123 continue;
124 if ((p = i->i_pspec) == NULL)
125 continue;
126 locspace += p->p_iattr->a_loclen;
127 }
128
129 /* Allocate and pack loc[]. */
130 locators.vec = ecalloc((size_t)locspace, sizeof(*locators.vec));
131 locators.used = 0;
132 packlocs();
133 }
134
135 /*
136 * Pack device instances together wherever possible.
137 */
138 static void
packdevi(void)139 packdevi(void)
140 {
141 struct devi *firststar, *i, **ip, *l, *p;
142 struct devbase *d;
143 u_short j, m, n;
144
145 /*
146 * Sort all the cloning units to after the non-cloning units,
147 * preserving order of cloning and non-cloning units with
148 * respect to other units of the same type.
149 *
150 * Algorithm: Walk down the list until the first cloning unit is
151 * seen for the second time (or until the end of the list, if there
152 * are no cloning units on the list), moving starred units to the
153 * end of the list.
154 */
155 TAILQ_FOREACH(d, &allbases, d_next) {
156 ip = &d->d_ihead;
157 firststar = NULL;
158
159 for (i = *ip; i != firststar; i = *ip) {
160 if (i->i_unit != STAR) {
161 /* try i->i_bsame next */
162 ip = &i->i_bsame;
163 } else {
164 if (firststar == NULL)
165 firststar = i;
166
167 *d->d_ipp = i;
168 d->d_ipp = &i->i_bsame;
169
170 *ip = i->i_bsame;
171 i->i_bsame = NULL;
172
173 /* leave ip alone; try (old) i->i_bsame next */
174 }
175 }
176 }
177
178 packed = ecalloc((size_t)ndevi + 1, sizeof *packed);
179 n = 0;
180 TAILQ_FOREACH(d, &allbases, d_next) {
181 /*
182 * For each instance of each device, add or collapse
183 * all its aliases.
184 *
185 * Pseudo-devices have a non-empty d_ihead for convenience.
186 * Ignore them.
187 */
188 if (d->d_ispseudo)
189 continue;
190 for (i = d->d_ihead; i != NULL; i = i->i_bsame) {
191 m = n;
192 for (l = i; l != NULL; l = l->i_alias) {
193 if (l->i_active != DEVI_ACTIVE
194 || i->i_pseudoroot)
195 continue;
196 l->i_locoff = -1;
197 /* try to find an equivalent for l */
198 for (j = m; j < n; j++) {
199 p = packed[j];
200 if (sameas(l, p)) {
201 l->i_collapsed = 1;
202 l->i_cfindex = p->i_cfindex;
203 goto nextalias;
204 }
205 }
206 /* could not find a suitable alias */
207 l->i_collapsed = 0;
208 l->i_cfindex = n;
209 packed[n++] = l;
210 nextalias:;
211 }
212 }
213 }
214 npacked = n;
215 packed[n] = NULL;
216 }
217
218 /*
219 * Return true if two aliases are "the same". In this case, they need
220 * to have the same parent spec, have the same config flags, and have
221 * the same locators.
222 */
223 static int
sameas(struct devi * i1,struct devi * i2)224 sameas(struct devi *i1, struct devi *i2)
225 {
226 const char **p1, **p2;
227
228 if (i1->i_pspec != i2->i_pspec)
229 return (0);
230 if (i1->i_cfflags != i2->i_cfflags)
231 return (0);
232 for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++)
233 if (*p1++ == 0)
234 return (1);
235 return (0);
236 }
237
238 static void
packlocs(void)239 packlocs(void)
240 {
241 struct pspec *ps;
242 struct devi **p, *i;
243 int l,o;
244 extern int Pflag;
245
246 qsort(packed, npacked, sizeof *packed, loclencmp);
247 for (p = packed; (i = *p) != NULL; p++) {
248 if ((ps = i->i_pspec) != NULL &&
249 (l = ps->p_iattr->a_loclen) > 0) {
250 if (Pflag) {
251 o = findvec(i->i_locs,
252 LOCHASH(i->i_locs[l - 1]), l,
253 samelocs, locators.used);
254 i->i_locoff = o < 0 ?
255 addlocs(i->i_locs, l) : o;
256 } else
257 i->i_locoff = addlocs(i->i_locs, l);
258 } else
259 i->i_locoff = -1;
260 }
261 resettails();
262 }
263
264 /*
265 * Return the index at which the given vector already exists, or -1
266 * if it is not anywhere in the current set. If we return -1, we assume
267 * our caller will add it at the end of the current set, and we make
268 * sure that next time, we will find it there.
269 */
270 static int
findvec(const void * ptr,int hash,int len,vec_cmp_func cmp,int nextplace)271 findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
272 {
273 struct tails *t, **hp;
274 int off;
275
276 hp = &tails[hash];
277 for (t = *hp; t != NULL; t = t->t_next) {
278 off = t->t_ends_at - len;
279 if (off >= 0 && (*cmp)(ptr, off, len))
280 return (off);
281 }
282 t = ecalloc(1, sizeof(*t));
283 t->t_next = *hp;
284 *hp = t;
285 t->t_ends_at = nextplace + len;
286 return (-1);
287 }
288
289 /*
290 * Comparison function for locators.
291 */
292 static int
samelocs(const void * ptr,int off,int len)293 samelocs(const void *ptr, int off, int len)
294 {
295 const char * const *p, * const *q;
296
297 for (p = &locators.vec[off], q = (const char * const *)ptr; --len >= 0;)
298 if (*p++ != *q++)
299 return (0); /* different */
300 return (1); /* same */
301 }
302
303 /*
304 * Add the given locators at the end of the global loc[] table.
305 */
306 static int
addlocs(const char ** locs,int len)307 addlocs(const char **locs, int len)
308 {
309 const char **p;
310 int ret;
311
312 ret = locators.used;
313 if ((locators.used = ret + len) > locspace)
314 panic("addlocs: overrun");
315 for (p = &locators.vec[ret]; --len >= 0;)
316 *p++ = *locs++;
317 return (ret);
318 }
319
320 /*
321 * Comparison function for qsort-by-locator-length, longest first.
322 *
323 * In the event of equality, break ties by i_cfindex, which should be
324 * unique, obviating the need for a stable sort.
325 */
326 static int
loclencmp(const void * a,const void * b)327 loclencmp(const void *a, const void *b)
328 {
329 const struct devi *const *d1p = a, *d1 = *d1p;
330 const struct devi *const *d2p = b, *d2 = *d2p;
331 const struct pspec *p1, *p2;
332 int l1, l2;
333
334 p1 = d1->i_pspec;
335 l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0;
336
337 p2 = d2->i_pspec;
338 l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0;
339
340 /*
341 * Longer locators first; among equal locator lengths, earliest
342 * index first.
343 */
344 if (l2 < l1)
345 return -1;
346 else if (l2 > l1)
347 return +1;
348 else if (d2->i_cfindex > d1->i_cfindex)
349 return -1;
350 else if (d2->i_cfindex < d1->i_cfindex)
351 return +1;
352 else
353 abort(); /* no ties possible */
354 }
355
356 static void
resettails(void)357 resettails(void)
358 {
359 struct tails **p, *t, *next;
360 int i;
361
362 for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
363 for (t = *p; t != NULL; t = next) {
364 next = t->t_next;
365 free(t);
366 }
367 *p = NULL;
368 }
369 }
370