Linux dm中minor number的管理——idr

1. idr机制

Linux的dm中对minor number采用idr机制进行管理。idr即"ID Radix",内核中通过radix树对ID进行组织和管理，是一种将整数ID和指针关联在一起的一种机制。radix树基于以二进制表示的键值的查找树，尤其适合于处理非常长的、可变长度的键值。查找时每个节点都存储有进行下一次的bit测试之前需要跳过的bit数目，查找效率比较高。

以下代码中的注释说明了idr的基本作用（lib/idr.c）
/*
 * 2002-10-18  written by Jim Houston [e-mail]
 *  Copyright (C) 2002 by Concurrent Computer Corporation
 *  Distributed under the GNU GPL license version 2.
 *
 * Modified by George Anzinger to reuse immediately and to use
 * find bit instructions.  Also removed _irq on spinlocks.
 *
 * Small id to pointer translation service. 
 *
 * It uses a radix tree like structure as a sparse array indexed
 * by the id to obtain the pointer.  The bitmap makes allocating
 * a new id quick. 
 *
 * You call it to allocate an id (an int) an associate with that id a
 * pointer or what ever, we treat it as a (void *).  You can pass this
 * id to a user for him to pass back at a later time.  You then pass
 * that id to this code and it returns your pointer.
   
 * You can release ids at any time. When all ids are released, most of
 * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
 * don't need to go to the memory "store" during an id allocate, just
 * so you don't need to be too concerned about locking and conflicts
 * with the slab allocator.
 */

API函数主要是以下几个：

void *idr_find(struct idr *idp, int id);
int idr_pre_get(struct idr *idp, unsigned gfp_mask);
int idr_get_new(struct idr *idp, void *ptr, int *id);
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
void idr_remove(struct idr *idp, int id);
void idr_init(struct idr *idp);


/**
 * idr_get_new - allocate new idr entry
 * @idp: idr handle
 * @ptr: pointer you want associated with the ide
 * @id: pointer to the allocated handle
 *
 * This is the allocate id function.  It should be called with any
 * required locks.
 * 
 * If memory is required, it will return -EAGAIN, you should unlock
 * and go back to the idr_pre_get() call.  If the idr is full, it will
 * return -ENOSPC.
 *
 * @id returns a value in the range 0 ... 0x7fffffff
 */
int idr_get_new(struct idr *idp, void *ptr, int *id)
{  
    int rv;
    rv = idr_get_new_above_int(idp, ptr, 0);
    /*
     * This is a cheap hack until the IDR code can be fixed to
     * return proper error values.
     */
    if (rv < 0) {
        if (rv == -1)
            return -EAGAIN;
        else /* Will be -3 */
            return -ENOSPC;
    }
    *id = rv;
    return 0;
}      


2. dm中minor的管理

/* 
 * Allocate and initialise a blank device with a given minor.
 */
static struct mapped_device *alloc_dev(unsigned int minor, int persistent)
{
    int r;
    struct mapped_device *md = kmalloc(sizeof(*md), GFP_KERNEL);

    if (!md) {
        DMWARN("unable to allocate device, out of memory.");
        return NULL;
    }

    /* get a minor number for the dev */
    r = persistent ? specific_minor(minor) : next_free_minor(&minor);

    blk_queue_make_request(md->queue, dm_request);

    md->disk = alloc_disk(1);

    md->disk->major = _major;
    md->disk->first_minor = minor;
    md->disk->queue = md->queue;

    sprintf(md->disk->disk_name, "dm-%d", minor);
    add_disk(md->disk);

    init_waitqueue_head(&md->wait);
    init_waitqueue_head(&md->eventq);
}

1）对于指定minor

/*
 * See if the device with a specific minor # is free.
 */
static int specific_minor(unsigned int minor)
{
    int r, m;

    if (minor >= (1 << MINORBITS))
        return -EINVAL;

    down(&_minor_lock);

    if (idr_find(&_minor_idr, minor)) {
        r = -EBUSY;
        goto out;
    }

    r = idr_pre_get(&_minor_idr, GFP_KERNEL);
    if (!r) {
        r = -ENOMEM;
        goto out;
    }

    r = idr_get_new_above(&_minor_idr, specific_minor, minor, &m);
    if (r) {
        goto out;
    }

    if (m != minor) {
        idr_remove(&_minor_idr, m);
        r = -EBUSY;
        goto out;
    }

out:
    up(&_minor_lock);
    return r;
}

2）动态分配minor

static int next_free_minor(unsigned int *minor)
{
    int r;
    unsigned int m;

    down(&_minor_lock);

    r = idr_pre_get(&_minor_idr, GFP_KERNEL);
    if (!r) {
        r = -ENOMEM;
        goto out;
    }

    r = idr_get_new(&_minor_idr, next_free_minor, &m);
    if (r) {
        goto out;
    }

    if (m >= (1 << MINORBITS)) {
        idr_remove(&_minor_idr, m);
        r = -ENOSPC;
        goto out;
    }

    *minor = m;

out:
    up(&_minor_lock);
    return r;
}


3）ioctl
static int dev_create(struct dm_ioctl *param, size_t param_size)
{      
    int r;
    struct mapped_device *md;

    r = check_name(param->name);
    if (r)   
        return r;
   
    if (param->flags & DM_PERSISTENT_DEV_FLAG)
        r = dm_create_with_minor(MINOR(huge_decode_dev(param->dev)), &md);
    else
        r = dm_create(&md);
}