usr.bin/config/pack.c

   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 * const *p, * const *q;
 292
 293         for (p = &locators.vec[off], q = (const char * const *)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 * const *)a)->i_pspec;
 327         l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0;
 328
 329         p2 = (*(const struct devi * const *)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 }