1 /* $NetBSD: pack.c,v 1.5 2007/01/13 23:47:36 christos 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/param.h> 48 #include <stdlib.h> 49 #include <string.h> 50 #include <util.h> 51 #include "defs.h" 52 53 /* 54 * Packing. We have three separate kinds of packing here. 55 * 56 * First, we pack device instances which have identical parent specs. 57 * 58 * Second, we pack locators. Given something like 59 * 60 * hp0 at mba0 drive 0 61 * hp* at mba* drive ? 62 * ht0 at mba0 drive 0 63 * tu0 at ht0 slave 0 64 * ht* at mba* drive ? 65 * tu* at ht* slave ? 66 * 67 * (where the default drive and slave numbers are -1), we have three 68 * locators whose value is 0 and three whose value is -1. Rather than 69 * emitting six integers, we emit just two. 70 * 71 * When packing locators, we would like to find sequences such as 72 * {1 2 3} {2 3 4} {3} {4 5} 73 * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence 74 * given by the appropriate offset (here 0, 1, 2, and 3 respectively). 75 * Non-overlapping packing is much easier, and so we use that here 76 * and miss out on the chance to squeeze the locator sequence optimally. 77 * (So it goes.) 78 */ 79 80 typedef int (*vec_cmp_func)(const void *, int, int); 81 82 #define TAILHSIZE 128 83 #define PVHASH(i) ((i) & (TAILHSIZE - 1)) 84 #define LOCHASH(l) (((long)(l) >> 2) & (TAILHSIZE - 1)) 85 struct tails { 86 struct tails *t_next; 87 int t_ends_at; 88 }; 89 90 static struct tails *tails[TAILHSIZE]; 91 static int locspace; 92 93 static void packdevi(void); 94 static void packlocs(void); 95 96 static int sameas(struct devi *, struct devi *); 97 static int findvec(const void *, int, int, vec_cmp_func, int); 98 static int samelocs(const void *, int, int); 99 static int addlocs(const char **, int); 100 static int loclencmp(const void *, const void *); 101 static void resettails(void); 102 103 void 104 pack(void) 105 { 106 struct pspec *p; 107 struct devi *i; 108 109 /* Pack instances and make parent vectors. */ 110 packdevi(); 111 112 /* 113 * Now that we know what we have, find upper limits on space 114 * needed for the loc[] table. The loc table size is bounded by 115 * what we would get if no packing occurred. 116 */ 117 locspace = 0; 118 TAILQ_FOREACH(i, &alldevi, i_next) { 119 if (!i->i_active == DEVI_ACTIVE || i->i_collapsed) 120 continue; 121 if ((p = i->i_pspec) == NULL) 122 continue; 123 locspace += p->p_iattr->a_loclen; 124 } 125 126 /* Allocate and pack loc[]. */ 127 locators.vec = ecalloc((size_t)locspace, sizeof(*locators.vec)); 128 locators.used = 0; 129 packlocs(); 130 } 131 132 /* 133 * Pack device instances together wherever possible. 134 */ 135 void 136 packdevi(void) 137 { 138 struct devi *firststar, *i, **ip, *l, *p; 139 struct devbase *d; 140 int j, m, n; 141 142 /* 143 * Sort all the cloning units to after the non-cloning units, 144 * preserving order of cloning and non-cloning units with 145 * respect to other units of the same type. 146 * 147 * Algorithm: Walk down the list until the first cloning unit is 148 * seen for the second time (or until the end of the list, if there 149 * are no cloning units on the list), moving starred units to the 150 * end of the list. 151 */ 152 TAILQ_FOREACH(d, &allbases, d_next) { 153 ip = &d->d_ihead; 154 firststar = NULL; 155 156 for (i = *ip; i != firststar; i = *ip) { 157 if (i->i_unit != STAR) { 158 /* try i->i_bsame next */ 159 ip = &i->i_bsame; 160 } else { 161 if (firststar == NULL) 162 firststar = i; 163 164 *d->d_ipp = i; 165 d->d_ipp = &i->i_bsame; 166 167 *ip = i->i_bsame; 168 i->i_bsame = NULL; 169 170 /* leave ip alone; try (old) i->i_bsame next */ 171 } 172 } 173 } 174 175 packed = ecalloc((size_t)ndevi + 1, sizeof *packed); 176 n = 0; 177 TAILQ_FOREACH(d, &allbases, d_next) { 178 /* 179 * For each instance of each device, add or collapse 180 * all its aliases. 181 * 182 * Pseudo-devices have a non-empty d_ihead for convenience. 183 * Ignore them. 184 */ 185 if (d->d_ispseudo) 186 continue; 187 for (i = d->d_ihead; i != NULL; i = i->i_bsame) { 188 m = n; 189 for (l = i; l != NULL; l = l->i_alias) { 190 if (l->i_active != DEVI_ACTIVE) 191 continue; 192 l->i_locoff = -1; 193 /* try to find an equivalent for l */ 194 for (j = m; j < n; j++) { 195 p = packed[j]; 196 if (sameas(l, p)) { 197 l->i_collapsed = 1; 198 l->i_cfindex = p->i_cfindex; 199 goto nextalias; 200 } 201 } 202 /* could not find a suitable alias */ 203 l->i_collapsed = 0; 204 l->i_cfindex = n; 205 packed[n++] = l; 206 nextalias:; 207 } 208 } 209 } 210 npacked = n; 211 packed[n] = NULL; 212 } 213 214 /* 215 * Return true if two aliases are "the same". In this case, they need 216 * to have the same parent spec, have the same config flags, and have 217 * the same locators. 218 */ 219 static int 220 sameas(struct devi *i1, struct devi *i2) 221 { 222 const char **p1, **p2; 223 224 if (i1->i_pspec != i2->i_pspec) 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 static void 235 packlocs(void) 236 { 237 struct pspec *ps; 238 struct devi **p, *i; 239 int l,o; 240 extern int Pflag; 241 242 qsort(packed, npacked, sizeof *packed, loclencmp); 243 for (p = packed; (i = *p) != NULL; p++) { 244 if ((ps = i->i_pspec) != NULL && 245 (l = ps->p_iattr->a_loclen) > 0) { 246 if (Pflag) { 247 o = findvec(i->i_locs, 248 LOCHASH(i->i_locs[l - 1]), l, 249 samelocs, locators.used); 250 i->i_locoff = o < 0 ? 251 addlocs(i->i_locs, l) : o; 252 } else 253 i->i_locoff = addlocs(i->i_locs, l); 254 } else 255 i->i_locoff = -1; 256 } 257 resettails(); 258 } 259 260 /* 261 * Return the index at which the given vector already exists, or -1 262 * if it is not anywhere in the current set. If we return -1, we assume 263 * our caller will add it at the end of the current set, and we make 264 * sure that next time, we will find it there. 265 */ 266 static int 267 findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace) 268 { 269 struct tails *t, **hp; 270 int off; 271 272 hp = &tails[hash]; 273 for (t = *hp; t != NULL; t = t->t_next) { 274 off = t->t_ends_at - len; 275 if (off >= 0 && (*cmp)(ptr, off, len)) 276 return (off); 277 } 278 t = ecalloc(1, sizeof(*t)); 279 t->t_next = *hp; 280 *hp = t; 281 t->t_ends_at = nextplace + len; 282 return (-1); 283 } 284 285 /* 286 * Comparison function for locators. 287 */ 288 static int 289 samelocs(const void *ptr, int off, int len) 290 { 291 const char **p, **q; 292 293 for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;) 294 if (*p++ != *q++) 295 return (0); /* different */ 296 return (1); /* same */ 297 } 298 299 /* 300 * Add the given locators at the end of the global loc[] table. 301 */ 302 static int 303 addlocs(const char **locs, int len) 304 { 305 const char **p; 306 int ret; 307 308 ret = locators.used; 309 if ((locators.used = ret + len) > locspace) 310 panic("addlocs: overrun"); 311 for (p = &locators.vec[ret]; --len >= 0;) 312 *p++ = *locs++; 313 return (ret); 314 } 315 316 /* 317 * Comparison function for qsort-by-locator-length, longest first. 318 * We rashly assume that subtraction of these lengths does not overflow. 319 */ 320 static int 321 loclencmp(const void *a, const void *b) 322 { 323 const struct pspec *p1, *p2; 324 int l1, l2; 325 326 p1 = (*(const struct devi **)a)->i_pspec; 327 l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0; 328 329 p2 = (*(const struct devi **)b)->i_pspec; 330 l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0; 331 332 return (l2 - l1); 333 } 334 335 static void 336 resettails(void) 337 { 338 struct tails **p, *t, *next; 339 int i; 340 341 for (p = tails, i = TAILHSIZE; --i >= 0; p++) { 342 for (t = *p; t != NULL; t = next) { 343 next = t->t_next; 344 free(t); 345 } 346 *p = NULL; 347 } 348 } 349