1 /* $OpenBSD: pack.c,v 1.14 2003/06/28 04:55:07 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 <sys/param.h> 45 #include <stdlib.h> 46 #include <string.h> 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 = emalloc(locspace * sizeof(*locators.vec)); 146 locators.used = 0; 147 packlocs(); 148 149 /* Allocate and pack pv[]. */ 150 parents.vec = emalloc(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 = emalloc((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 = emalloc(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 = emalloc(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 = erealloc(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 = emalloc(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) panic("packpvec"); 349 par = i->i_parents; 350 for (v = 0; v < l; v++) 351 vec[v] = par[v]->i_cfindex; 352 if (l == 0 || 353 (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 } 504