src/system/kernel/device_manager/id_generator.cpp

   1 /*
   2  * Copyright 2004-2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
   3  * Copyright 2002-2004, Thomas Kurschel. All rights reserved.
   4  *
   5  * Distributed under the terms of the MIT License.
   6  */
   7
   8 /*!     Generators are created on demand and deleted if all their
   9         IDs are freed. They have a ref_count which is increased
  10         whenever someone messes with the generator.
  11
  12         Whenever a generator is searched for, generator_lock is held.
  13
  14         To find out which ID are allocated, a bitmap is used that
  15         contain up to GENERATOR_MAX_ID bits. This is a hard limit,
  16         but it's simple to implement. If someone really needs lots of
  17         IDs, we can still rewrite the code. For simplicity, we use
  18         sGeneratorLock instead of a generator specific lock during
  19         allocation; changing it is straightforward as everything
  20         is prepared for that.
  21 */
  22
  23
  24 #include "id_generator.h"
  25
  26 #include <new>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include <KernelExport.h>
  31
  32 #include <util/AutoLock.h>
  33 #include <util/DoublyLinkedList.h>
  34
  35
  36 //#define TRACE_ID_GENERATOR
  37 #ifdef TRACE_ID_GENERATOR
  38 #       define TRACE(x) dprintf x
  39 #else
  40 #       define TRACE(x) ;
  41 #endif
  42
  43 #define GENERATOR_MAX_ID 64
  44
  45 struct id_generator : DoublyLinkedListLinkImpl<id_generator> {
  46         id_generator(const char* name)
  47                 :
  48                 ref_count(1),
  49                 name(strdup(name)),
  50                 num_ids(0)
  51         {
  52                 memset(&alloc_map, 0, sizeof(alloc_map));
  53         }
  54
  55         ~id_generator()
  56         {
  57                 free(name);
  58         }
  59
  60         int32           ref_count;
  61         char*           name;
  62         uint32          num_ids;
  63         uint8           alloc_map[(GENERATOR_MAX_ID + 7) / 8];
  64 };
  65
  66 typedef DoublyLinkedList<id_generator> GeneratorList;
  67
  68
  69 GeneratorList sGenerators;
  70 static mutex sLock = MUTEX_INITIALIZER("id generator");
  71
  72
  73 /*!     Create new generator.
  74         sLock must be held.
  75 */
  76 static id_generator*
  77 create_generator(const char* name)
  78 {
  79         TRACE(("create_generator(name: %s)\n", name));
  80
  81         id_generator* generator = new(std::nothrow) id_generator(name);
  82         if (generator == NULL)
  83                 return NULL;
  84
  85         if (generator->name == NULL) {
  86                 delete generator;
  87                 return NULL;
  88         }
  89
  90         sGenerators.Add(generator);
  91         return generator;
  92 }
  93
  94
  95 /*! Allocate ID */
  96 static int32
  97 create_id_internal(id_generator* generator)
  98 {
  99         uint32 id;
 100
 101         TRACE(("create_id_internal(name: %s)\n", generator->name));
 102
 103         // see above: we use global instead of local lock
 104         MutexLocker _(sLock);
 105
 106         // simple bit search
 107         for (id = 0; id < GENERATOR_MAX_ID; ++id) {
 108                 if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) {
 109                         TRACE(("  id: %lu\n", id));
 110
 111                         generator->alloc_map[id / 8] |= 1 << (id & 7);
 112                         generator->num_ids++;
 113
 114                         return id;
 115                 }
 116         }
 117
 118         return B_ERROR;
 119 }
 120
 121
 122 /*!     Gets a generator by name, and acquires a reference to it.
 123         sLock must be held.
 124 */
 125 static id_generator*
 126 get_generator(const char* name)
 127 {
 128         TRACE(("find_generator(name: %s)\n", name));
 129
 130         GeneratorList::Iterator iterator = sGenerators.GetIterator();
 131         while (iterator.HasNext()) {
 132                 id_generator* generator = iterator.Next();
 133
 134                 if (!strcmp(generator->name, name)) {
 135                         // increase ref_count, so it won't go away
 136                         generator->ref_count++;
 137                         return generator;
 138                 }
 139         }
 140
 141         return NULL;
 142 }
 143
 144
 145 /*! Decrease ref_count, deleting generator if not used anymore */
 146 static void
 147 release_generator(id_generator *generator)
 148 {
 149         TRACE(("release_generator(name: %s)\n", generator->name));
 150
 151         MutexLocker _(sLock);
 152
 153         if (--generator->ref_count == 0) {
 154                 // no one messes with generator
 155                 if (generator->num_ids == 0) {
 156                         TRACE(("  Destroy %s\n", generator->name));
 157                         // no IDs is allocated - destroy generator
 158                         sGenerators.Remove(generator);
 159                         delete generator;
 160                 }
 161         }
 162 }
 163
 164
 165 //      #pragma mark - Private kernel API
 166
 167
 168 void
 169 dm_init_id_generator(void)
 170 {
 171         new(&sGenerators) GeneratorList;
 172 }
 173
 174
 175 //      #pragma mark - Public module API
 176
 177
 178 /*! Create automatic ID */
 179 int32
 180 dm_create_id(const char* name)
 181 {
 182
 183         // find generator, create new if not there
 184         mutex_lock(&sLock);
 185
 186         id_generator* generator = get_generator(name);
 187         if (generator == NULL)
 188                 generator = create_generator(name);
 189
 190         mutex_unlock(&sLock);
 191
 192         if (generator == NULL)
 193                 return B_NO_MEMORY;
 194
 195         // get ID
 196         int32 id = create_id_internal(generator);
 197
 198         release_generator(generator);
 199
 200         TRACE(("dm_create_id: name: %s, id: %ld\n", name, id));
 201         return id;
 202 }
 203
 204
 205 /*!     Free automatically generated ID */
 206 status_t
 207 dm_free_id(const char* name, uint32 id)
 208 {
 209         TRACE(("dm_free_id(name: %s, id: %ld)\n", name, id));
 210
 211         // find generator
 212         mutex_lock(&sLock);
 213
 214         id_generator* generator = get_generator(name);
 215
 216         mutex_unlock(&sLock);
 217
 218         if (generator == NULL) {
 219                 TRACE(("  Generator %s doesn't exist\n", name));
 220                 return B_NAME_NOT_FOUND;
 221         }
 222
 223         // free ID
 224
 225         // make sure it's really allocated
 226         // (very important to keep <num_ids> in sync
 227         if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) {
 228                 dprintf("id %" B_PRIu32 " of generator %s wasn't allocated\n", id,
 229                         generator->name);
 230
 231                 release_generator(generator);
 232                 return B_BAD_VALUE;
 233         }
 234
 235         generator->alloc_map[id / 8] &= ~(1 << (id & 7));
 236         generator->num_ids--;
 237
 238         release_generator(generator);
 239         return B_OK;
 240 }