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