diff options
Diffstat (limited to 'usr.sbin/config.new/pack.c')
| -rw-r--r-- | usr.sbin/config.new/pack.c | 520 |
1 files changed, 520 insertions, 0 deletions
diff --git a/usr.sbin/config.new/pack.c b/usr.sbin/config.new/pack.c new file mode 100644 index 0000000..8b525ec --- /dev/null +++ b/usr.sbin/config.new/pack.c @@ -0,0 +1,520 @@ +/* + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * This software was developed by the Computer Systems Engineering group + * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and + * contributed to Berkeley. + * + * All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Lawrence Berkeley Laboratories. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)pack.c 8.1 (Berkeley) 6/6/93 + */ + +#include <sys/param.h> +#include <stdlib.h> +#include <string.h> +#include "config.h" + +/* + * Packing. We have three separate kinds of packing here. + * + * First, we pack device instances, to collapse things like + * + * uba0 at sbi0 nexus ? + * uba0 at bi0 nexus ? + * + * into a single instance that is "at sbi0 or bi0". + * + * Second, we pack locators. Given something like + * + * hp0 at mba0 drive 0 + * hp* at mba* drive ? + * ht0 at mba0 drive 0 + * tu0 at ht0 slave 0 + * ht* at mba* drive ? + * tu* at ht* slave ? + * + * (where the default drive and slave numbers are -1), we have three + * locators whose value is 0 and three whose value is -1. Rather than + * emitting six integers, we emit just two. + * + * Finally, we pack parent vectors. This is very much like packing + * locators. Unlike locators, however, parent vectors are always + * terminated by -1 (rather like the way C strings always end with + * a NUL). + * + * When packing locators, we would like to find sequences such as + * {1 2 3} {2 3 4} {3} {4 5} + * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence + * given by the appropriate offset (here 0, 1, 2, and 3 respectively). + * When we pack parent vectors, overlap of this sort is impossible. + * Non-overlapping packing is much easier, and so we use that here + * and miss out on the chance to squeeze the locator sequence optimally. + * (So it goes.) + */ + +typedef int (*vec_cmp_func) __P((const void *, int, int)); + +#define TAILHSIZE 128 +#define PVHASH(i) ((i) & (TAILHSIZE - 1)) +#define LOCHASH(l) (((int)(l) >> 2) & (TAILHSIZE - 1)) +struct tails { + struct tails *t_next; + int t_ends_at; +}; + +static struct tails *tails[TAILHSIZE]; +static int locspace; +static int pvecspace; +static int longest_pvec; + +static void packdevi __P((void)); +static void packlocs __P((void)); +static void packpvec __P((void)); + +static void addparents __P((struct devi *src, struct devi *dst)); +static int nparents __P((struct devi **, struct devbase *, int)); +static int sameas __P((struct devi *, struct devi *)); +static int findvec __P((const void *, int, int, vec_cmp_func, int)); +static int samelocs __P((const void *, int, int)); +static int addlocs __P((const char **, int)); +static int loclencmp __P((const void *, const void *)); +static int samepv __P((const void *, int, int)); +static int addpv __P((short *, int)); +static int pvlencmp __P((const void *, const void *)); +static void resettails __P((void)); + +void +pack() +{ + register struct devi *i; + register int n; + + /* Pack instances and make parent vectors. */ + packdevi(); + + /* + * Now that we know what we have, find upper limits on space + * needed for the loc[] and pv[] tables, and find the longest + * single pvec. The loc and pv table sizes are bounded by + * what we would get if no packing occurred. + */ + locspace = pvecspace = 0; + for (i = alldevi; i != NULL; i = i->i_next) { + if (i->i_collapsed) + continue; + locspace += i->i_atattr->a_loclen; + n = i->i_pvlen + 1; + if (n > longest_pvec) + longest_pvec = n; + pvecspace += n; + } + + /* Allocate and pack loc[]. */ + locators.vec = emalloc(locspace * sizeof(*locators.vec)); + locators.used = 0; + packlocs(); + + /* Allocate and pack pv[]. */ + parents.vec = emalloc(pvecspace * sizeof(*parents.vec)); + parents.used = 0; + packpvec(); +} + +/* + * Pack instances together wherever possible. When everything is + * packed, go back and set up the parents for each. We must do this + * on a second pass because during the first one, we do not know which, + * if any, of the parents will collapse during packing. + */ +void +packdevi() +{ + register struct devi *i, *l, *p; + register struct devbase *d; + register int j, m, n; + + packed = emalloc((ndevi + 1) * sizeof *packed); + n = 0; + for (d = allbases; d != NULL; d = d->d_next) { + /* + * For each instance of each device, add or collapse + * all its aliases. + */ + for (i = d->d_ihead; i != NULL; i = i->i_bsame) { + m = n; + for (l = i; l != NULL; l = l->i_alias) { + l->i_pvlen = 0; + l->i_pvoff = -1; + l->i_locoff = -1; + l->i_ivoff = -1; + /* try to find an equivalent for l */ + for (j = m; j < n; j++) { + p = packed[j]; + if (sameas(l, p)) { + l->i_collapsed = 1; + l->i_cfindex = p->i_cfindex; + goto nextalias; + } + } + /* could not find a suitable alias */ + l->i_collapsed = 0; + l->i_cfindex = n; + l->i_parents = emalloc(sizeof(*l->i_parents)); + l->i_parents[0] = NULL; + packed[n++] = l; + nextalias:; + } + } + } + npacked = n; + packed[n] = NULL; + for (i = alldevi; i != NULL; i = i->i_next) + addparents(i, packed[i->i_cfindex]); +} + +/* + * Return true if two aliases are "the same". In this case, they need + * to have the same config flags and the same locators. + */ +static int +sameas(i1, i2) + register struct devi *i1, *i2; +{ + register const char **p1, **p2; + + if (i1->i_cfflags != i2->i_cfflags) + return (0); + for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++) + if (*p1++ == 0) + return (1); + return 0; +} + +/* + * Add the parents associated with "src" to the (presumably uncollapsed) + * instance "dst". + */ +static void +addparents(src, dst) + register struct devi *src, *dst; +{ + register struct nvlist *nv; + register struct devi *i, **p, **q; + register int j, n, old, new, ndup; + + if (dst->i_collapsed) + panic("addparents() i_collapsed"); + + /* Collect up list of parents to add. */ + if (src->i_at == NULL) /* none, 'cuz "at root" */ + return; + if (src->i_atdev != NULL) { + n = nparents(NULL, src->i_atdev, src->i_atunit); + p = emalloc(n * sizeof *p); + if (n == 0) + return; + (void)nparents(p, src->i_atdev, src->i_atunit); + } else { + n = 0; + for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next) + n += nparents(NULL, nv->nv_ptr, src->i_atunit); + if (n == 0) + return; + p = emalloc(n * sizeof *p); + n = 0; + for (nv = src->i_atattr->a_refs; nv != NULL; nv = nv->nv_next) + n += nparents(p + n, nv->nv_ptr, src->i_atunit); + } + /* Now elide duplicates. */ + ndup = 0; + for (j = 0; j < n; j++) { + i = p[j]; + for (q = dst->i_parents; *q != NULL; q++) { + if (*q == i) { + ndup++; + p[j] = NULL; + break; + } + } + } + /* Finally, add all the non-duplicates. */ + old = dst->i_pvlen; + new = old + (n - ndup); + if (old > new) + panic("addparents() old > new"); + if (old == new) { + free(p); + return; + } + dst->i_parents = q = erealloc(dst->i_parents, (new + 1) * sizeof(*q)); + dst->i_pvlen = new; + q[new] = NULL; + q += old; + for (j = 0; j < n; j++) + if (p[j] != NULL) + *q++ = p[j]; + free(p); +} + +/* + * Count up parents, and optionally store pointers to each. + */ +static int +nparents(p, dev, unit) + register struct devi **p; + register struct devbase *dev; + register int unit; +{ + register struct devi *i, *l; + register int n; + + n = 0; + /* for each instance ... */ + for (i = dev->d_ihead; i != NULL; i = i->i_bsame) { + /* ... take each un-collapsed alias */ + for (l = i; l != NULL; l = l->i_alias) { + if (!l->i_collapsed && + (unit == WILD || unit == l->i_unit)) { + if (p != NULL) + *p++ = l; + n++; + } + } + } + return (n); +} + +static void +packlocs() +{ + register struct devi **p, *i; + register int l, o; + + qsort(packed, npacked, sizeof *packed, loclencmp); + for (p = packed; (i = *p) != NULL; p++) { + if ((l = i->i_atattr->a_loclen) > 0) { + o = findvec(i->i_locs, LOCHASH(i->i_locs[l - 1]), l, + samelocs, locators.used); + i->i_locoff = o < 0 ? addlocs(i->i_locs, l) : o; + } else + i->i_locoff = -1; + } + resettails(); +} + +static void +packpvec() +{ + register struct devi **p, *i, **par; + register int l, v, o; + register short *vec; + + vec = emalloc(longest_pvec * sizeof(*vec)); + qsort(packed, npacked, sizeof *packed, pvlencmp); + for (p = packed; (i = *p) != NULL; p++) { + l = i->i_pvlen; +if (l > longest_pvec) panic("packpvec"); + par = i->i_parents; + for (v = 0; v < l; v++) + vec[v] = par[v]->i_cfindex; + if (l == 0 || + (o = findvec(vec, PVHASH(vec[l - 1]), l, + samepv, parents.used)) < 0) + o = addpv(vec, l); + i->i_pvoff = o; + } + free(vec); + resettails(); +} + +/* + * Return the index at which the given vector already exists, or -1 + * if it is not anywhere in the current set. If we return -1, we assume + * our caller will add it at the end of the current set, and we make + * sure that next time, we will find it there. + */ +static int +findvec(ptr, hash, len, cmp, nextplace) + const void *ptr; + int hash, len; + vec_cmp_func cmp; + int nextplace; +{ + register struct tails *t, **hp; + register int off; + + hp = &tails[hash]; + for (t = *hp; t != NULL; t = t->t_next) { + off = t->t_ends_at - len; + if (off >= 0 && (*cmp)(ptr, off, len)) + return (off); + } + t = emalloc(sizeof(*t)); + t->t_next = *hp; + *hp = t; + t->t_ends_at = nextplace + len; + return (-1); +} + +/* + * Comparison function for locators. + */ +static int +samelocs(ptr, off, len) + const void *ptr; + int off; + register int len; +{ + register const char **p, **q; + + for (p = &locators.vec[off], q = (const char **)ptr; --len >= 0;) + if (*p++ != *q++) + return (0); /* different */ + return (1); /* same */ +} + +/* + * Add the given locators at the end of the global loc[] table. + */ +static int +addlocs(locs, len) + register const char **locs; + register int len; +{ + register const char **p; + register int ret; + + ret = locators.used; + if ((locators.used = ret + len) > locspace) + panic("addlocs: overrun"); + for (p = &locators.vec[ret]; --len >= 0;) + *p++ = *locs++; + return (ret); +} + +/* + * Comparison function for qsort-by-locator-length, longest first. + * We rashly assume that subtraction of these lengths does not overflow. + */ +static int +loclencmp(a, b) + const void *a, *b; +{ + register int l1, l2; + + l1 = (*(struct devi **)a)->i_atattr->a_loclen; + l2 = (*(struct devi **)b)->i_atattr->a_loclen; + return (l2 - l1); +} + +/* + * Comparison function for parent vectors. + */ +static int +samepv(ptr, off, len) + const void *ptr; + int off; + register int len; +{ + register short *p, *q; + + for (p = &parents.vec[off], q = (short *)ptr; --len >= 0;) + if (*p++ != *q++) + return (0); /* different */ + return (1); /* same */ +} + +/* + * Add the given parent vectors at the end of the global pv[] table. + */ +static int +addpv(pv, len) + register short *pv; + register int len; +{ + register short *p; + register int ret; + static int firstend = -1; + + /* + * If the vector is empty, reuse the first -1. It will be + * there if there are any nonempty vectors at all, since we + * do the longest first. If there are no nonempty vectors, + * something is probably wrong, but we will ignore that here. + */ + if (len == 0 && firstend >= 0) + return (firstend); + len++; /* account for trailing -1 */ + ret = parents.used; + if ((parents.used = ret + len) > pvecspace) + panic("addpv: overrun"); + for (p = &parents.vec[ret]; --len > 0;) + *p++ = *pv++; + *p = -1; + if (firstend < 0) + firstend = parents.used - 1; + return (ret); +} + +/* + * Comparison function for qsort-by-parent-vector-length, longest first. + * We rashly assume that subtraction of these lengths does not overflow. + */ +static int +pvlencmp(a, b) + const void *a, *b; +{ + register int l1, l2; + + l1 = (*(struct devi **)a)->i_pvlen; + l2 = (*(struct devi **)b)->i_pvlen; + return (l2 - l1); +} + +static void +resettails() +{ + register struct tails **p, *t, *next; + register int i; + + for (p = tails, i = TAILHSIZE; --i >= 0; p++) { + for (t = *p; t != NULL; t = next) { + next = t->t_next; + free(t); + } + *p = NULL; + } +} |
