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