* 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
* 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
* @(#)pack.c 8.1 (Berkeley) 6/6/93
* Packing. We have three separate kinds of packing here.
* First, we pack device instances, to collapse things like
* into a single instance that is "at sbi0 or bi0".
* Second, we pack locators. Given something like
* (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
* 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.
typedef int (*vec_cmp_func
) __P((const void *, int, int));
#define PVHASH(i) ((i) & (TAILHSIZE - 1))
#define LOCHASH(l) (((int)(l) >> 2) & (TAILHSIZE - 1))
static struct tails
*tails
[TAILHSIZE
];
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));
/* Pack instances and make parent vectors. */
* 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
) {
locspace
+= i
->i_atattr
->a_loclen
;
/* Allocate and pack loc[]. */
locators
.vec
= emalloc(locspace
* sizeof(*locators
.vec
));
/* Allocate and pack pv[]. */
parents
.vec
= emalloc(pvecspace
* sizeof(*parents
.vec
));
* 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.
register struct devi
*i
, *l
, *p
;
register struct devbase
*d
;
packed
= emalloc((ndevi
+ 1) * sizeof *packed
);
for (d
= allbases
; d
!= NULL
; d
= d
->d_next
) {
* For each instance of each device, add or collapse
for (i
= d
->d_ihead
; i
!= NULL
; i
= i
->i_bsame
) {
for (l
= i
; l
!= NULL
; l
= l
->i_alias
) {
/* try to find an equivalent for l */
for (j
= m
; j
< n
; j
++) {
l
->i_cfindex
= p
->i_cfindex
;
/* could not find a suitable alias */
l
->i_parents
= emalloc(sizeof(*l
->i_parents
));
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.
register struct devi
*i1
, *i2
;
register const char **p1
, **p2
;
if (i1
->i_cfflags
!= i2
->i_cfflags
)
for (p1
= i1
->i_locs
, p2
= i2
->i_locs
; *p1
== *p2
; p2
++)
* Add the parents associated with "src" to the (presumably uncollapsed)
register struct devi
*src
, *dst
;
register struct nvlist
*nv
;
register struct devi
*i
, **p
, **q
;
register int j
, n
, old
, new, ndup
;
panic("addparents() i_collapsed");
/* Collect up list of parents to add. */
if (src
->i_at
== NULL
) /* none, 'cuz "at root" */
if (src
->i_atdev
!= NULL
) {
n
= nparents(NULL
, src
->i_atdev
, src
->i_atunit
);
p
= emalloc(n
* sizeof *p
);
(void)nparents(p
, src
->i_atdev
, src
->i_atunit
);
for (nv
= src
->i_atattr
->a_refs
; nv
!= NULL
; nv
= nv
->nv_next
)
n
+= nparents(NULL
, nv
->nv_ptr
, src
->i_atunit
);
p
= emalloc(n
* sizeof *p
);
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. */
for (j
= 0; j
< n
; j
++) {
for (q
= dst
->i_parents
; *q
!= NULL
; q
++) {
/* Finally, add all the non-duplicates. */
panic("addparents() old > new");
dst
->i_parents
= q
= erealloc(dst
->i_parents
, (new + 1) * sizeof(*q
));
* Count up parents, and optionally store pointers to each.
register struct devi
**p
;
register struct devbase
*dev
;
register struct devi
*i
, *l
;
/* 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
) {
(unit
== WILD
|| unit
== l
->i_unit
)) {
register struct devi
**p
, *i
;
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
;
register struct devi
**p
, *i
, **par
;
vec
= emalloc(longest_pvec
* sizeof(*vec
));
qsort(packed
, npacked
, sizeof *packed
, pvlencmp
);
for (p
= packed
; (i
= *p
) != NULL
; p
++) {
if (l
> longest_pvec
) panic("packpvec");
vec
[v
] = par
[v
]->i_cfindex
;
(o
= findvec(vec
, PVHASH(vec
[l
- 1]), l
,
samepv
, parents
.used
)) < 0)
* 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.
findvec(ptr
, hash
, len
, cmp
, nextplace
)
register struct tails
*t
, **hp
;
for (t
= *hp
; t
!= NULL
; t
= t
->t_next
) {
off
= t
->t_ends_at
- len
;
if (off
>= 0 && (*cmp
)(ptr
, off
, len
))
t
->t_ends_at
= nextplace
+ len
;
* Comparison function for locators.
register const char **p
, **q
;
for (p
= &locators
.vec
[off
], q
= (const char **)ptr
; --len
>= 0;)
return (0); /* different */
* Add the given locators at the end of the global loc[] table.
register const char **locs
;
if ((locators
.used
= ret
+ len
) > locspace
)
panic("addlocs: overrun");
for (p
= &locators
.vec
[ret
]; --len
>= 0;)
* Comparison function for qsort-by-locator-length, longest first.
* We rashly assume that subtraction of these lengths does not overflow.
l1
= (*(struct devi
**)a
)->i_atattr
->a_loclen
;
l2
= (*(struct devi
**)b
)->i_atattr
->a_loclen
;
* Comparison function for parent vectors.
for (p
= &parents
.vec
[off
], q
= (short *)ptr
; --len
>= 0;)
return (0); /* different */
* Add the given parent vectors at the end of the global pv[] table.
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)
len
++; /* account for trailing -1 */
if ((parents
.used
= ret
+ len
) > pvecspace
)
for (p
= &parents
.vec
[ret
]; --len
> 0;)
firstend
= parents
.used
- 1;
* Comparison function for qsort-by-parent-vector-length, longest first.
* We rashly assume that subtraction of these lengths does not overflow.
l1
= (*(struct devi
**)a
)->i_pvlen
;
l2
= (*(struct devi
**)b
)->i_pvlen
;
register struct tails
**p
, *t
, *next
;
for (p
= tails
, i
= TAILHSIZE
; --i
>= 0; p
++) {
for (t
= *p
; t
!= NULL
; t
= next
) {