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