1*7c0971f0Sjoerg /* $NetBSD: pack.c,v 1.10 2015/09/12 19:11:13 joerg Exp $ */
25ecc953bSthorpej
35ecc953bSthorpej /*
45ecc953bSthorpej * Copyright (c) 1992, 1993
55ecc953bSthorpej * The Regents of the University of California. All rights reserved.
65ecc953bSthorpej *
75ecc953bSthorpej * This software was developed by the Computer Systems Engineering group
85ecc953bSthorpej * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
95ecc953bSthorpej * contributed to Berkeley.
105ecc953bSthorpej *
115ecc953bSthorpej * All advertising materials mentioning features or use of this software
125ecc953bSthorpej * must display the following acknowledgement:
135ecc953bSthorpej * This product includes software developed by the University of
145ecc953bSthorpej * California, Lawrence Berkeley Laboratories.
155ecc953bSthorpej *
165ecc953bSthorpej * Redistribution and use in source and binary forms, with or without
175ecc953bSthorpej * modification, are permitted provided that the following conditions
185ecc953bSthorpej * are met:
195ecc953bSthorpej * 1. Redistributions of source code must retain the above copyright
205ecc953bSthorpej * notice, this list of conditions and the following disclaimer.
215ecc953bSthorpej * 2. Redistributions in binary form must reproduce the above copyright
225ecc953bSthorpej * notice, this list of conditions and the following disclaimer in the
235ecc953bSthorpej * documentation and/or other materials provided with the distribution.
245ecc953bSthorpej * 3. Neither the name of the University nor the names of its contributors
255ecc953bSthorpej * may be used to endorse or promote products derived from this software
265ecc953bSthorpej * without specific prior written permission.
275ecc953bSthorpej *
285ecc953bSthorpej * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
295ecc953bSthorpej * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
305ecc953bSthorpej * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
315ecc953bSthorpej * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
325ecc953bSthorpej * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
335ecc953bSthorpej * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
345ecc953bSthorpej * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
355ecc953bSthorpej * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
365ecc953bSthorpej * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
375ecc953bSthorpej * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
385ecc953bSthorpej * SUCH DAMAGE.
395ecc953bSthorpej *
405ecc953bSthorpej * from: @(#)pack.c 8.1 (Berkeley) 6/6/93
415ecc953bSthorpej */
425ecc953bSthorpej
435ecc953bSthorpej #if HAVE_NBTOOL_CONFIG_H
445ecc953bSthorpej #include "nbtool_config.h"
455ecc953bSthorpej #endif
465ecc953bSthorpej
479a7f4bbaSchristos #include <sys/cdefs.h>
48*7c0971f0Sjoerg __RCSID("$NetBSD: pack.c,v 1.10 2015/09/12 19:11:13 joerg Exp $");
499a7f4bbaSchristos
505ecc953bSthorpej #include <sys/param.h>
515ecc953bSthorpej #include <stdlib.h>
525ecc953bSthorpej #include <string.h>
53d0fb8901Schristos #include <util.h>
545ecc953bSthorpej #include "defs.h"
555ecc953bSthorpej
565ecc953bSthorpej /*
575ecc953bSthorpej * Packing. We have three separate kinds of packing here.
585ecc953bSthorpej *
595ecc953bSthorpej * First, we pack device instances which have identical parent specs.
605ecc953bSthorpej *
615ecc953bSthorpej * Second, we pack locators. Given something like
625ecc953bSthorpej *
635ecc953bSthorpej * hp0 at mba0 drive 0
645ecc953bSthorpej * hp* at mba* drive ?
655ecc953bSthorpej * ht0 at mba0 drive 0
665ecc953bSthorpej * tu0 at ht0 slave 0
675ecc953bSthorpej * ht* at mba* drive ?
685ecc953bSthorpej * tu* at ht* slave ?
695ecc953bSthorpej *
705ecc953bSthorpej * (where the default drive and slave numbers are -1), we have three
715ecc953bSthorpej * locators whose value is 0 and three whose value is -1. Rather than
725ecc953bSthorpej * emitting six integers, we emit just two.
735ecc953bSthorpej *
745ecc953bSthorpej * When packing locators, we would like to find sequences such as
755ecc953bSthorpej * {1 2 3} {2 3 4} {3} {4 5}
765ecc953bSthorpej * and turn this into the flat sequence {1 2 3 4 5}, with each subsequence
775ecc953bSthorpej * given by the appropriate offset (here 0, 1, 2, and 3 respectively).
785ecc953bSthorpej * Non-overlapping packing is much easier, and so we use that here
795ecc953bSthorpej * and miss out on the chance to squeeze the locator sequence optimally.
805ecc953bSthorpej * (So it goes.)
815ecc953bSthorpej */
825ecc953bSthorpej
835ecc953bSthorpej typedef int (*vec_cmp_func)(const void *, int, int);
845ecc953bSthorpej
855ecc953bSthorpej #define TAILHSIZE 128
865ecc953bSthorpej #define PVHASH(i) ((i) & (TAILHSIZE - 1))
875ecc953bSthorpej #define LOCHASH(l) (((long)(l) >> 2) & (TAILHSIZE - 1))
885ecc953bSthorpej struct tails {
895ecc953bSthorpej struct tails *t_next;
905ecc953bSthorpej int t_ends_at;
915ecc953bSthorpej };
925ecc953bSthorpej
935ecc953bSthorpej static struct tails *tails[TAILHSIZE];
945ecc953bSthorpej static int locspace;
955ecc953bSthorpej
965ecc953bSthorpej static void packdevi(void);
975ecc953bSthorpej static void packlocs(void);
985ecc953bSthorpej
995ecc953bSthorpej static int sameas(struct devi *, struct devi *);
1005ecc953bSthorpej static int findvec(const void *, int, int, vec_cmp_func, int);
1015ecc953bSthorpej static int samelocs(const void *, int, int);
1025ecc953bSthorpej static int addlocs(const char **, int);
1035ecc953bSthorpej static int loclencmp(const void *, const void *);
1045ecc953bSthorpej static void resettails(void);
1055ecc953bSthorpej
1065ecc953bSthorpej void
pack(void)1075ecc953bSthorpej pack(void)
1085ecc953bSthorpej {
1095ecc953bSthorpej struct pspec *p;
1105ecc953bSthorpej struct devi *i;
1115ecc953bSthorpej
1125ecc953bSthorpej /* Pack instances and make parent vectors. */
1135ecc953bSthorpej packdevi();
1145ecc953bSthorpej
1155ecc953bSthorpej /*
1165ecc953bSthorpej * Now that we know what we have, find upper limits on space
1175ecc953bSthorpej * needed for the loc[] table. The loc table size is bounded by
1185ecc953bSthorpej * what we would get if no packing occurred.
1195ecc953bSthorpej */
1205ecc953bSthorpej locspace = 0;
1215ecc953bSthorpej TAILQ_FOREACH(i, &alldevi, i_next) {
122*7c0971f0Sjoerg if (i->i_active != DEVI_ACTIVE || i->i_collapsed)
1235ecc953bSthorpej continue;
1245ecc953bSthorpej if ((p = i->i_pspec) == NULL)
1255ecc953bSthorpej continue;
1265ecc953bSthorpej locspace += p->p_iattr->a_loclen;
1275ecc953bSthorpej }
1285ecc953bSthorpej
1295ecc953bSthorpej /* Allocate and pack loc[]. */
130c7295a4cSchristos locators.vec = ecalloc((size_t)locspace, sizeof(*locators.vec));
1315ecc953bSthorpej locators.used = 0;
1325ecc953bSthorpej packlocs();
1335ecc953bSthorpej }
1345ecc953bSthorpej
1355ecc953bSthorpej /*
1365ecc953bSthorpej * Pack device instances together wherever possible.
1375ecc953bSthorpej */
13883003414Spooka static void
packdevi(void)1395ecc953bSthorpej packdevi(void)
1405ecc953bSthorpej {
1415ecc953bSthorpej struct devi *firststar, *i, **ip, *l, *p;
1425ecc953bSthorpej struct devbase *d;
1439a7f4bbaSchristos u_short j, m, n;
1445ecc953bSthorpej
1455ecc953bSthorpej /*
1465ecc953bSthorpej * Sort all the cloning units to after the non-cloning units,
1475ecc953bSthorpej * preserving order of cloning and non-cloning units with
1485ecc953bSthorpej * respect to other units of the same type.
1495ecc953bSthorpej *
1505ecc953bSthorpej * Algorithm: Walk down the list until the first cloning unit is
1515ecc953bSthorpej * seen for the second time (or until the end of the list, if there
1525ecc953bSthorpej * are no cloning units on the list), moving starred units to the
1535ecc953bSthorpej * end of the list.
1545ecc953bSthorpej */
1555ecc953bSthorpej TAILQ_FOREACH(d, &allbases, d_next) {
1565ecc953bSthorpej ip = &d->d_ihead;
1575ecc953bSthorpej firststar = NULL;
1585ecc953bSthorpej
1595ecc953bSthorpej for (i = *ip; i != firststar; i = *ip) {
1605ecc953bSthorpej if (i->i_unit != STAR) {
1615ecc953bSthorpej /* try i->i_bsame next */
1625ecc953bSthorpej ip = &i->i_bsame;
1635ecc953bSthorpej } else {
1645ecc953bSthorpej if (firststar == NULL)
1655ecc953bSthorpej firststar = i;
1665ecc953bSthorpej
1675ecc953bSthorpej *d->d_ipp = i;
1685ecc953bSthorpej d->d_ipp = &i->i_bsame;
1695ecc953bSthorpej
1705ecc953bSthorpej *ip = i->i_bsame;
1715ecc953bSthorpej i->i_bsame = NULL;
1725ecc953bSthorpej
1735ecc953bSthorpej /* leave ip alone; try (old) i->i_bsame next */
1745ecc953bSthorpej }
1755ecc953bSthorpej }
1765ecc953bSthorpej }
1775ecc953bSthorpej
178c7295a4cSchristos packed = ecalloc((size_t)ndevi + 1, sizeof *packed);
1795ecc953bSthorpej n = 0;
1805ecc953bSthorpej TAILQ_FOREACH(d, &allbases, d_next) {
1815ecc953bSthorpej /*
1825ecc953bSthorpej * For each instance of each device, add or collapse
1835ecc953bSthorpej * all its aliases.
184c130d400Scube *
185c130d400Scube * Pseudo-devices have a non-empty d_ihead for convenience.
186c130d400Scube * Ignore them.
1875ecc953bSthorpej */
188c130d400Scube if (d->d_ispseudo)
189c130d400Scube continue;
1905ecc953bSthorpej for (i = d->d_ihead; i != NULL; i = i->i_bsame) {
1915ecc953bSthorpej m = n;
1925ecc953bSthorpej for (l = i; l != NULL; l = l->i_alias) {
19390ac64deSpooka if (l->i_active != DEVI_ACTIVE
19490ac64deSpooka || i->i_pseudoroot)
195c130d400Scube continue;
1965ecc953bSthorpej l->i_locoff = -1;
1975ecc953bSthorpej /* try to find an equivalent for l */
1985ecc953bSthorpej for (j = m; j < n; j++) {
1995ecc953bSthorpej p = packed[j];
2005ecc953bSthorpej if (sameas(l, p)) {
2015ecc953bSthorpej l->i_collapsed = 1;
2025ecc953bSthorpej l->i_cfindex = p->i_cfindex;
2035ecc953bSthorpej goto nextalias;
2045ecc953bSthorpej }
2055ecc953bSthorpej }
2065ecc953bSthorpej /* could not find a suitable alias */
2075ecc953bSthorpej l->i_collapsed = 0;
2085ecc953bSthorpej l->i_cfindex = n;
2095ecc953bSthorpej packed[n++] = l;
2105ecc953bSthorpej nextalias:;
2115ecc953bSthorpej }
2125ecc953bSthorpej }
2135ecc953bSthorpej }
2145ecc953bSthorpej npacked = n;
2155ecc953bSthorpej packed[n] = NULL;
2165ecc953bSthorpej }
2175ecc953bSthorpej
2185ecc953bSthorpej /*
2195ecc953bSthorpej * Return true if two aliases are "the same". In this case, they need
2205ecc953bSthorpej * to have the same parent spec, have the same config flags, and have
2215ecc953bSthorpej * the same locators.
2225ecc953bSthorpej */
2235ecc953bSthorpej static int
sameas(struct devi * i1,struct devi * i2)2245ecc953bSthorpej sameas(struct devi *i1, struct devi *i2)
2255ecc953bSthorpej {
2265ecc953bSthorpej const char **p1, **p2;
2275ecc953bSthorpej
2285ecc953bSthorpej if (i1->i_pspec != i2->i_pspec)
2295ecc953bSthorpej return (0);
2305ecc953bSthorpej if (i1->i_cfflags != i2->i_cfflags)
2315ecc953bSthorpej return (0);
2325ecc953bSthorpej for (p1 = i1->i_locs, p2 = i2->i_locs; *p1 == *p2; p2++)
2335ecc953bSthorpej if (*p1++ == 0)
2345ecc953bSthorpej return (1);
2355ecc953bSthorpej return (0);
2365ecc953bSthorpej }
2375ecc953bSthorpej
2385ecc953bSthorpej static void
packlocs(void)2395ecc953bSthorpej packlocs(void)
2405ecc953bSthorpej {
2415ecc953bSthorpej struct pspec *ps;
2425ecc953bSthorpej struct devi **p, *i;
2435ecc953bSthorpej int l,o;
2445ecc953bSthorpej extern int Pflag;
2455ecc953bSthorpej
2465ecc953bSthorpej qsort(packed, npacked, sizeof *packed, loclencmp);
2475ecc953bSthorpej for (p = packed; (i = *p) != NULL; p++) {
2485ecc953bSthorpej if ((ps = i->i_pspec) != NULL &&
2495ecc953bSthorpej (l = ps->p_iattr->a_loclen) > 0) {
2505ecc953bSthorpej if (Pflag) {
2515ecc953bSthorpej o = findvec(i->i_locs,
2525ecc953bSthorpej LOCHASH(i->i_locs[l - 1]), l,
2535ecc953bSthorpej samelocs, locators.used);
2545ecc953bSthorpej i->i_locoff = o < 0 ?
2555ecc953bSthorpej addlocs(i->i_locs, l) : o;
2565ecc953bSthorpej } else
2575ecc953bSthorpej i->i_locoff = addlocs(i->i_locs, l);
2585ecc953bSthorpej } else
2595ecc953bSthorpej i->i_locoff = -1;
2605ecc953bSthorpej }
2615ecc953bSthorpej resettails();
2625ecc953bSthorpej }
2635ecc953bSthorpej
2645ecc953bSthorpej /*
2655ecc953bSthorpej * Return the index at which the given vector already exists, or -1
2665ecc953bSthorpej * if it is not anywhere in the current set. If we return -1, we assume
2675ecc953bSthorpej * our caller will add it at the end of the current set, and we make
2685ecc953bSthorpej * sure that next time, we will find it there.
2695ecc953bSthorpej */
2705ecc953bSthorpej static int
findvec(const void * ptr,int hash,int len,vec_cmp_func cmp,int nextplace)2715ecc953bSthorpej findvec(const void *ptr, int hash, int len, vec_cmp_func cmp, int nextplace)
2725ecc953bSthorpej {
2735ecc953bSthorpej struct tails *t, **hp;
2745ecc953bSthorpej int off;
2755ecc953bSthorpej
2765ecc953bSthorpej hp = &tails[hash];
2775ecc953bSthorpej for (t = *hp; t != NULL; t = t->t_next) {
2785ecc953bSthorpej off = t->t_ends_at - len;
2795ecc953bSthorpej if (off >= 0 && (*cmp)(ptr, off, len))
2805ecc953bSthorpej return (off);
2815ecc953bSthorpej }
2825ecc953bSthorpej t = ecalloc(1, sizeof(*t));
2835ecc953bSthorpej t->t_next = *hp;
2845ecc953bSthorpej *hp = t;
2855ecc953bSthorpej t->t_ends_at = nextplace + len;
2865ecc953bSthorpej return (-1);
2875ecc953bSthorpej }
2885ecc953bSthorpej
2895ecc953bSthorpej /*
2905ecc953bSthorpej * Comparison function for locators.
2915ecc953bSthorpej */
2925ecc953bSthorpej static int
samelocs(const void * ptr,int off,int len)2935ecc953bSthorpej samelocs(const void *ptr, int off, int len)
2945ecc953bSthorpej {
2955cc303e1Slukem const char * const *p, * const *q;
2965ecc953bSthorpej
2975cc303e1Slukem for (p = &locators.vec[off], q = (const char * const *)ptr; --len >= 0;)
2985ecc953bSthorpej if (*p++ != *q++)
2995ecc953bSthorpej return (0); /* different */
3005ecc953bSthorpej return (1); /* same */
3015ecc953bSthorpej }
3025ecc953bSthorpej
3035ecc953bSthorpej /*
3045ecc953bSthorpej * Add the given locators at the end of the global loc[] table.
3055ecc953bSthorpej */
3065ecc953bSthorpej static int
addlocs(const char ** locs,int len)3075ecc953bSthorpej addlocs(const char **locs, int len)
3085ecc953bSthorpej {
3095ecc953bSthorpej const char **p;
3105ecc953bSthorpej int ret;
3115ecc953bSthorpej
3125ecc953bSthorpej ret = locators.used;
3135ecc953bSthorpej if ((locators.used = ret + len) > locspace)
3145ecc953bSthorpej panic("addlocs: overrun");
3155ecc953bSthorpej for (p = &locators.vec[ret]; --len >= 0;)
3165ecc953bSthorpej *p++ = *locs++;
3175ecc953bSthorpej return (ret);
3185ecc953bSthorpej }
3195ecc953bSthorpej
3205ecc953bSthorpej /*
3215ecc953bSthorpej * Comparison function for qsort-by-locator-length, longest first.
3225ecc953bSthorpej * We rashly assume that subtraction of these lengths does not overflow.
3235ecc953bSthorpej */
3245ecc953bSthorpej static int
loclencmp(const void * a,const void * b)3255ecc953bSthorpej loclencmp(const void *a, const void *b)
3265ecc953bSthorpej {
327c7295a4cSchristos const struct pspec *p1, *p2;
3285ecc953bSthorpej int l1, l2;
3295ecc953bSthorpej
3305cc303e1Slukem p1 = (*(const struct devi * const *)a)->i_pspec;
3315ecc953bSthorpej l1 = p1 != NULL ? p1->p_iattr->a_loclen : 0;
3325ecc953bSthorpej
3335cc303e1Slukem p2 = (*(const struct devi * const *)b)->i_pspec;
3345ecc953bSthorpej l2 = p2 != NULL ? p2->p_iattr->a_loclen : 0;
3355ecc953bSthorpej
3365ecc953bSthorpej return (l2 - l1);
3375ecc953bSthorpej }
3385ecc953bSthorpej
3395ecc953bSthorpej static void
resettails(void)3405ecc953bSthorpej resettails(void)
3415ecc953bSthorpej {
3425ecc953bSthorpej struct tails **p, *t, *next;
3435ecc953bSthorpej int i;
3445ecc953bSthorpej
3455ecc953bSthorpej for (p = tails, i = TAILHSIZE; --i >= 0; p++) {
3465ecc953bSthorpej for (t = *p; t != NULL; t = next) {
3475ecc953bSthorpej next = t->t_next;
3485ecc953bSthorpej free(t);
3495ecc953bSthorpej }
3505ecc953bSthorpej *p = NULL;
3515ecc953bSthorpej }
3525ecc953bSthorpej }
353