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 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 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 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 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 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 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 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 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 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
Indexes created Sat Sep 20 22:09:52 GMT 2025