From owner-freebsd-hackers@FreeBSD.ORG  Wed Feb 11 12:53:59 2009
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@FreeBSD.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 39BFC106566C
	for <freebsd-hackers@FreeBSD.org>; Wed, 11 Feb 2009 12:53:59 +0000 (UTC)
	(envelope-from avg@icyb.net.ua)
Received: from citadel.icyb.net.ua (citadel.icyb.net.ua [212.40.38.140])
	by mx1.freebsd.org (Postfix) with ESMTP id 7433F8FC15
	for <freebsd-hackers@FreeBSD.org>; Wed, 11 Feb 2009 12:53:58 +0000 (UTC)
	(envelope-from avg@icyb.net.ua)
Received: from odyssey.starpoint.kiev.ua (alpha-e.starpoint.kiev.ua
	[212.40.38.101])
	by citadel.icyb.net.ua (8.8.8p3/ICyb-2.3exp) with ESMTP id OAA11321
	for <freebsd-hackers@FreeBSD.org>; Wed, 11 Feb 2009 14:53:56 +0200 (EET)
	(envelope-from avg@icyb.net.ua)
Message-ID: <4992CA63.8080601@icyb.net.ua>
Date: Wed, 11 Feb 2009 14:53:55 +0200
From: Andriy Gapon <avg@icyb.net.ua>
User-Agent: Thunderbird 2.0.0.19 (X11/20090110)
MIME-Version: 1.0
To: freebsd-hackers@FreeBSD.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Cc: 
Subject: generalizing fd allocation code to id allocation
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 11 Feb 2009 12:53:59 -0000


Guys,

anybody has ideas (or code) for generalizing code in
sys/kern/kern_descrip.c for managing fd-s ("small" integer numbers)?

I mean divorcing that code from filedesc and making it re-usable
wherever we need some (constrained) id allocation.
By constrained I mean that either ids are allocated from a sufficiently
small limited pool or it is desirable to keep ids at small values.

I needed this in a small driver that I am slowly writing and here's some
bits from it:

#define NDSLOTTYPE      uint64_t
#define NDSLOTSIZE      sizeof(NDSLOTTYPE)
#define NDENTRIES       (NDSLOTSIZE * __CHAR_BIT)
#define NDSLOT(x)       ((x) / NDENTRIES)
#define NDBIT(x)        ((NDSLOTTYPE)1 << ((x) % NDENTRIES))
#define NDSLOTS(x)      (((x) + NDENTRIES - 1) / NDENTRIES)
...
/* XXX ugly */
NDSLOTTYPE host_addr_map[NDSLOTS(sizeof(uint8_t) * __CHAR_BIT)];
...
static uint8_t alloc_host_addr(struct heci_softc *sc)
{
        static const int maxoff = sizeof(sc->host_addr_map) /
sizeof(sc->host_addr_map[0]);
        NDSLOTTYPE *map = sc->host_addr_map;
        int off;

        for (off = 0; off < maxoff; ++off) {
                if (map[off] != ~0UL) {
                        uint8_t addr = off * NDENTRIES + ffsl(~map[off])
- 1;
                        map[NDSLOT(addr)] |= NDBIT(addr);
                        return (addr);
                }
        }

        /* XXX what to return if all addresses are in use? */
        /* use the fact that zero is a reserved address */
        return 0;
}

static void
release_host_addr(struct heci_softc *sc, uint8_t addr)
{
        NDSLOTTYPE *map = sc->host_addr_map;
        if (!(map[NDSLOT(addr)] & NDBIT(addr))) /* XXX make KASSERT? */
                device_printf(sc->dev, "release for unused host addr
0x%02x\n", addr);
        map[NDSLOT(addr)] &= ~NDBIT(addr);
}


Essentially this is almost a copy/paste.


-- 
Andriy Gapon