1 /* $OpenBSD: pack.c,v 1.16 2011/10/02 22:20:50 edd 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 46 #include <stdlib.h> 47 #include <string.h> 48 49 #include "config.h" 50 51 /* 52 * Packing. We have three separate kinds of packing here. 53 * 54 * First, we pack device instances, to collapse things like 55 * 56 * uba0 at sbi0 nexus ? 57 * uba0 at bi0 nexus ? 58 * 59 * into a single instance that is "at sbi0 or bi0". 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 * Finally, we pack parent vectors. This is very much like packing 75 * locators. Unlike locators, however, parent vectors are always 76 * terminated by -1 (rather like the way C strings always end with 77 * a NUL). 78 * 79 * When packing locators, we would like to find sequences such as 80 * {1 2 3} {2 3 4} {3} {4 5} 81 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence 82 * given by the appropriate offset (here 0, 1, 2, and 3 respectively). 83 * When we pack parent vectors, overlap of this sort is impossible. 84 * Non-overlapping packing is much easier, and so we use that here 85 * and miss out on the chance to squeeze the locator sequence optimally. 86 * (So it goes.) 87 */ 88 89 typedef int (*vec_cmp_func)(const void *, int, int); 90 91 #define TAILHSIZE 128 92 #define PVHASH(i) ((i) & (TAILHSIZE - 1)) 93 #define LOCHASH(l) (((long)(l) >> 2) & (TAILHSIZE - 1)) 94 struct tails { 95 struct tails *t_next; 96 int t_ends_at; 97 }; 98 99 static struct tails *tails[TAILHSIZE]; 100 static int locspace; 101 static int pvecspace; 102 static int longest_pvec; 103 104 static void packdevi(void); 105 static void packlocs(void); 106 static void packpvec(void); 107 108 static void addparents(struct devi *src, struct devi *dst); 109 static int nparents(struct devi **, struct devbase *, int); 110 static int sameas(struct devi *, struct devi *); 111 static int findvec(const void *, int, int, vec_cmp_func, int); 112 static int samelocs(const void *, int, int); 113 static int addlocs(const char **, int); 114 static int loclencmp(const void *, const void *); 115 static int samepv(const void *, int, int); 116 static int addpv(short *, int); 117 static int pvlencmp(const void *, const void *); 118 static void resettails(void); 119 120 void 121 pack(void) 122 { 123 struct devi *i; 124 int n; 125 126 /* Pack instances and make parent vectors. */ 127 packdevi(); 128 129 /* 130 * Now that we know what we have, find upper limits on space 131 * needed for the loc[] and pv[] tables, and find the longest 132 * single pvec. The loc and pv table sizes are bounded by 133 * what we would get if no packing occurred. 134 */ 135 locspace = pvecspace = 0; 136 for (i = alldevi; i != NULL; i = i->i_next) { 137 if (i->i_collapsed) 138 continue; 139 locspace += i->i_atattr->a_loclen; 140 n = i->i_pvlen + 1; 141 if (n > longest_pvec) 142 longest_pvec = n; 143 pvecspace += n; 144 } 145 146 /* Allocate and pack loc[]. */ 147 locators.vec = emalloc(locspace * sizeof(*locators.vec)); 148 locators.used = 0; 149 packlocs(); 150 151 /* Allocate and pack pv[]. */ 152 parents.vec = emalloc(pvecspace * sizeof(*parents.vec)); 153 parents.used = 0; 154 packpvec(); 155 } 156 157 /* 158 * Pack instances together wherever possible. When everything is 159 * packed, go back and set up the parents for each. We must do this 160 * on a second pass because during the first one, we do not know which, 161 * if any, of the parents will collapse during packing. 162 */ 163 void 164 packdevi(void) 165 { 166 struct devi *i, *l, *p; 167 struct deva *d; 168 int j, m, n; 169 170 packed = emalloc((ndevi + 1) * sizeof *packed); 171 n = 0; 172 for (d = alldevas; d != NULL; d = d->d_next) { 173 /* 174 * For each instance of each attachment, add or collapse 175 * all its aliases. 176 */ 177 for (i = d->d_ihead; i != NULL; i = i->i_asame) { 178 m = n; 179 for (l = i; l != NULL; l = l->i_alias) { 180 /* Skip if we already handled this one. */ 181 if (l->i_cfindex >= 0) 182 continue; 183 l->i_pvlen = 0; 184 l->i_pvoff = -1; 185 l->i_locoff = -1; 186 /* try to find an equivalent for l */ 187 for (j = m; j < n; j++) { 188 p = packed[j]; 189 if (sameas(l, p)) { 190 l->i_collapsed = 1; 191 l->i_cfindex = p->i_cfindex; 192 goto nextalias; 193 } 194 } 195 /* could not find a suitable alias */ 196 l->i_collapsed = 0; 197 l->i_cfindex = n; 198 l->i_parents = emalloc(sizeof(*l->i_parents)); 199 l->i_parents[0] = NULL; 200 packed[n++] = l; 201 nextalias:; 202 } 203 } 204 } 205 npacked = n; 206 packed[n] = NULL; 207 for (i = alldevi; i != NULL; i = i->i_next) 208 addparents(i, packed[i->i_cfindex]); 209 } 210 211 /* 212 * Return true if two aliases are "the same". In this case, they need 213 * to attach via the same attribute, have the same config flags, and 214 * have the same locators. 215 */ 216 static int 217 sameas(struct devi *i1, struct devi *i2) 218 { 219 const char **p1, **p2; 220 221 if (i1->i_atattr != i2->i_atattr) 222 return (0); 223 if (i1->i_cfflags != i2->i_cfflags) 224 return (0); 225 for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++) 226 if (*p1++ == 0) 227 return (1); 228 return 0; 229 } 230 231 /* 232 * Add the parents associated with "src" to the (presumably uncollapsed) 233 * instance "dst". 234 */ 235 static void 236 addparents(struct devi *src, struct devi *dst) 237 { 238 struct nvlist *nv; 239 struct devi *i, **p, **q; 240 int j, n, old, new, ndup; 241 242 if (dst->i_collapsed) 243 panic("addparents() i_collapsed"); 244 245 /* Collect up list of parents to add. */ 246 if (src->i_at == NULL) /* none, because we are "at root" */ 247 return; 248 if (src->i_atdev != NULL) { 249 n = nparents(NULL, src->i_atdev, src->i_atunit); 250 p = emalloc(n * sizeof *p); 251 if (n == 0) 252 return; 253 (void)nparents(p, src->i_atdev, src->i_atunit); 254 } else { 255 n = 0; 256 for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next) 257 n += nparents(NULL, nv->nv_ptr, src->i_atunit); 258 if (n == 0) 259 return; 260 p = emalloc(n * sizeof *p); 261 n = 0; 262 for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next) 263 n += nparents(p + n, nv->nv_ptr, src->i_atunit); 264 } 265 /* Now elide duplicates. */ 266 ndup = 0; 267 for (j = 0; j < n; j++) { 268 i = p[j]; 269 for (q = dst->i_parents; *q != NULL; q++) { 270 if (*q == i) { 271 ndup++; 272 p[j] = NULL; 273 break; 274 } 275 } 276 } 277 /* Finally, add all the non-duplicates. */ 278 old = dst->i_pvlen; 279 new = old + (n - ndup); 280 if (old > new) 281 panic("addparents() old > new"); 282 if (old == new) { 283 free(p); 284 return; 285 } 286 dst->i_parents = q = erealloc(dst->i_parents, (new + 1) * sizeof(*q)); 287 dst->i_pvlen = new; 288 q[new] = NULL; 289 q += old; 290 for (j = 0; j < n; j++) 291 if (p[j] != NULL) 292 *q++ = p[j]; 293 free(p); 294 } 295 296 /* 297 * Count up parents, and optionally store pointers to each. 298 */ 299 static int 300 nparents(struct devi **p, struct devbase *dev, int unit) 301 { 302 struct devi *i, *l; 303 int n; 304 305 n = 0; 306 /* for each instance ... */ 307 for (i = dev->d_ihead; i != NULL; i = i->i_bsame) { 308 /* ... take each un-collapsed alias */ 309 for (l = i; l != NULL; l = l->i_alias) { 310 if (!l->i_collapsed && 311 (unit == WILD || unit == l->i_unit)) { 312 if (p != NULL) 313 *p++ = l; 314 n++; 315 } 316 } 317 } 318 return (n); 319 } 320 321 static void 322 packlocs(void) 323 { 324 struct devi **p, *i; 325 int l, o; 326 327 qsort(packed, npacked, sizeof *packed, loclencmp); 328 for (p = packed; (i = *p) != NULL; p++) { 329 if ((l = i->i_atattr->a_loclen) > 0) { 330 o = findvec(i->i_locs, LOCHASH(i->i_locs[l - 1]), l, 331 samelocs, locators.used); 332 i->i_locoff = o < 0 ? addlocs(i->i_locs, l) : o; 333 } else 334 i->i_locoff = -1; 335 } 336 resettails(); 337 } 338 339 static void 340 packpvec(void) 341 { 342 struct devi **p, *i, **par; 343 int l, v, o; 344 short *vec; 345 346 vec = emalloc(longest_pvec * sizeof(*vec)); 347 qsort(packed, npacked, sizeof *packed, pvlencmp); 348 for (p = packed; (i = *p) != NULL; p++) { 349 l = i->i_pvlen; 350 if (l > longest_pvec) 351 panic("packpvec"); 352 par = i->i_parents; 353 for (v = 0; v < l; v++) 354 vec[v] = par[v]->i_cfindex; 355 if (l == 0 || (o = findvec(vec, PVHASH(vec[l - 1]), l, 356 samepv, parents.used)) < 0) 357 o = addpv(vec, l); 358 i->i_pvoff = o; 359 } 360 free(vec); 361 resettails(); 362 } 363 364 /* 365 * Return the index at which the given vector already exists, or -1 366 * if it is not anywhere in the current set. If we return -1, we assume 367 * our caller will add it at the end of the current set, and we make 368 * sure that next time, we will find it there. 369 */ 370 static int 371 findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace) 372 { 373 struct tails *t, **hp; 374 int off; 375 376 hp = &tails[hash]; 377 for (t = *hp; t != NULL; t = t->t_next) { 378 off = t->t_ends_at - len; 379 if (off >= 0 && (*cmp)(ptr, off, len)) 380 return (off); 381 } 382 t = emalloc(sizeof(*t)); 383 t->t_next = *hp; 384 *hp = t; 385 t->t_ends_at = nextplace + len; 386 return (-1); 387 } 388 389 /* 390 * Comparison function for locators. 391 */ 392 static int 393 samelocs(const void *ptr, int off, int len) 394 { 395 const char **p, **q; 396 397 for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;) 398 if (*p++ != *q++) 399 return (0); /* different */ 400 return (1); /* same */ 401 } 402 403 /* 404 * Add the given locators at the end of the global loc[] table. 405 */ 406 static int 407 addlocs(const char **locs, int len) 408 { 409 const char **p; 410 int ret; 411 412 ret = locators.used; 413 if ((locators.used = ret + len) > locspace) 414 panic("addlocs: overrun"); 415 for (p = &locators.vec[ret]; --len >= 0;) 416 *p++ = *locs++; 417 return (ret); 418 } 419 420 /* 421 * Comparison function for qsort-by-locator-length, longest first. 422 * We rashly assume that subtraction of these lengths does not overflow. 423 */ 424 static int 425 loclencmp(const void *a, const void *b) 426 { 427 int l1, l2; 428 429 l1 = (*(struct devi **)a)->i_atattr->a_loclen; 430 l2 = (*(struct devi **)b)->i_atattr->a_loclen; 431 return (l2 - l1); 432 } 433 434 /* 435 * Comparison function for parent vectors. 436 */ 437 static int 438 samepv(const void *ptr, int off, int len) 439 { 440 short *p, *q; 441 442 for (p = &parents.vec[off], q = (short *)ptr; --len >= 0;) 443 if (*p++ != *q++) 444 return (0); /* different */ 445 return (1); /* same */ 446 } 447 448 /* 449 * Add the given parent vectors at the end of the global pv[] table. 450 */ 451 static int 452 addpv(short *pv, int len) 453 { 454 short *p; 455 int ret; 456 static int firstend = -1; 457 458 /* 459 * If the vector is empty, reuse the first -1. It will be 460 * there if there are any nonempty vectors at all, since we 461 * do the longest first. If there are no nonempty vectors, 462 * something is probably wrong, but we will ignore that here. 463 */ 464 if (len == 0 && firstend >= 0) 465 return (firstend); 466 len++; /* account for trailing -1 */ 467 ret = parents.used; 468 if ((parents.used = ret + len) > pvecspace) 469 panic("addpv: overrun"); 470 for (p = &parents.vec[ret]; --len > 0;) 471 *p++ = *pv++; 472 *p = -1; 473 if (firstend < 0) 474 firstend = parents.used - 1; 475 return (ret); 476 } 477 478 /* 479 * Comparison function for qsort-by-parent-vector-length, longest first. 480 * We rashly assume that subtraction of these lengths does not overflow. 481 */ 482 static int 483 pvlencmp(const void *a, const void *b) 484 { 485 int l1, l2; 486 487 l1 = (*(struct devi **)a)->i_pvlen; 488 l2 = (*(struct devi **)b)->i_pvlen; 489 return (l2 - l1); 490 } 491 492 static void 493 resettails(void) 494 { 495 struct tails **p, *t, *next; 496 int i; 497 498 for (p = tails, i = TAILHSIZE; --i >= 0; p++) { 499 for (t = *p; t != NULL; t = next) { 500 next = t->t_next; 501 free(t); 502 } 503 *p = NULL; 504 } 505 } 506