1 /* $NetBSD: pack.c,v 1.1 2005/06/05 18:19:53 thorpej 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_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 for (i = d->d_ihead; i != NULL; i = i->i_bsame) { 182 m = n; 183 for (l = i; l != NULL; l = l->i_alias) { 184 l->i_locoff = -1; 185 /* try to find an equivalent for l */ 186 for (j = m; j < n; j++) { 187 p = packed[j]; 188 if (sameas(l, p)) { 189 l->i_collapsed = 1; 190 l->i_cfindex = p->i_cfindex; 191 goto nextalias; 192 } 193 } 194 /* could not find a suitable alias */ 195 l->i_collapsed = 0; 196 l->i_cfindex = n; 197 packed[n++] = l; 198 nextalias:; 199 } 200 } 201 } 202 npacked = n; 203 packed[n] = NULL; 204 } 205 206 /* 207 * Return true if two aliases are "the same". In this case, they need 208 * to have the same parent spec, have the same config flags, and have 209 * the same locators. 210 */ 211 static int 212 sameas(struct devi *i1, struct devi *i2) 213 { 214 const char **p1, **p2; 215 216 if (i1->i_pspec != i2->i_pspec) 217 return (0); 218 if (i1->i_cfflags != i2->i_cfflags) 219 return (0); 220 for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++) 221 if (*p1++ == 0) 222 return (1); 223 return (0); 224 } 225 226 static void 227 packlocs(void) 228 { 229 struct pspec *ps; 230 struct devi **p, *i; 231 int l,o; 232 extern int Pflag; 233 234 qsort(packed, npacked, sizeof *packed, loclencmp); 235 for (p = packed; (i = *p) != NULL; p++) { 236 if ((ps = i->i_pspec) != NULL && 237 (l = ps->p_iattr->a_loclen) > 0) { 238 if (Pflag) { 239 o = findvec(i->i_locs, 240 LOCHASH(i->i_locs[l - 1]), l, 241 samelocs, locators.used); 242 i->i_locoff = o < 0 ? 243 addlocs(i->i_locs, l) : o; 244 } else 245 i->i_locoff = addlocs(i->i_locs, l); 246 } else 247 i->i_locoff = -1; 248 } 249 resettails(); 250 } 251 252 /* 253 * Return the index at which the given vector already exists, or -1 254 * if it is not anywhere in the current set. If we return -1, we assume 255 * our caller will add it at the end of the current set, and we make 256 * sure that next time, we will find it there. 257 */ 258 static int 259 findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace) 260 { 261 struct tails *t, **hp; 262 int off; 263 264 hp = &tails[hash]; 265 for (t = *hp; t != NULL; t = t->t_next) { 266 off = t->t_ends_at - len; 267 if (off >= 0 && (*cmp)(ptr, off, len)) 268 return (off); 269 } 270 t = ecalloc(1, sizeof(*t)); 271 t->t_next = *hp; 272 *hp = t; 273 t->t_ends_at = nextplace + len; 274 return (-1); 275 } 276 277 /* 278 * Comparison function for locators. 279 */ 280 static int 281 samelocs(const void *ptr, int off, int len) 282 { 283 const char **p, **q; 284 285 for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;) 286 if (*p++ != *q++) 287 return (0); /* different */ 288 return (1); /* same */ 289 } 290 291 /* 292 * Add the given locators at the end of the global loc[] table. 293 */ 294 static int 295 addlocs(const char **locs, int len) 296 { 297 const char **p; 298 int ret; 299 300 ret = locators.used; 301 if ((locators.used = ret + len) > locspace) 302 panic("addlocs: overrun"); 303 for (p = &locators.vec[ret]; --len >= 0;) 304 *p++ = *locs++; 305 return (ret); 306 } 307 308 /* 309 * Comparison function for qsort-by-locator-length, longest first. 310 * We rashly assume that subtraction of these lengths does not overflow. 311 */ 312 static int 313 loclencmp(const void *a, const void *b) 314 { 315 struct pspec *p1, *p2; 316 int l1, l2; 317 318 p1 = (*(struct devi **)a)->i_pspec; 319 l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0; 320 321 p2 = (*(struct devi **)b)->i_pspec; 322 l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0; 323 324 return (l2 - l1); 325 } 326 327 static void 328 resettails(void) 329 { 330 struct tails **p, *t, *next; 331 int i; 332 333 for (p = tails, i = TAILHSIZE; --i >= 0; p++) { 334 for (t = *p; t != NULL; t = next) { 335 next = t->t_next; 336 free(t); 337 } 338 *p = NULL; 339 } 340 } 341