kitten/kernel/idspace.c

   1 /* Copyright (c) 2008, Sandia National Laboratories */
   2
   3 #include <lwk/kernel.h>
   4 #include <lwk/idspace.h>
   5 #include <lwk/log2.h>
   6 #include <arch/page.h>
   7
   8 struct idspace {
   9         id_t   min_id;
  10         id_t   max_id;
  11         size_t size;
  12         size_t ids_in_use;
  13         size_t offset;
  14         void * bitmap;
  15 };
  16
  17 static size_t
  18 calc_order(struct idspace *idspace)
  19 {
  20         size_t pages = DIV_ROUND_UP(idspace->size, PAGE_SIZE * 8);
  21         return roundup_pow_of_two(pages);
  22 }
  23
  24 int
  25 idspace_create(id_t min_id, id_t max_id, idspace_t *idspace)
  26 {
  27         struct idspace *spc;
  28
  29         if ((min_id == ANY_ID) || (max_id == ANY_ID))
  30                 return -EINVAL;
  31
  32         if (min_id > max_id)
  33                 return -EINVAL;
  34
  35         if (!idspace)
  36                 return -EINVAL;
  37
  38         if (!(spc = kmem_alloc(sizeof(*spc))))
  39                 return -ENOMEM;
  40
  41         spc->min_id     = min_id;
  42         spc->max_id     = max_id;
  43         spc->size       = max_id - min_id + 1;
  44         spc->ids_in_use = 0;
  45         spc->offset     = 0;
  46
  47         if (!(spc->bitmap = kmem_get_pages(calc_order(spc)))) {
  48                 kmem_free(spc);
  49                 return -ENOMEM;
  50         }
  51
  52         *idspace = spc;
  53
  54         return 0;
  55 }
  56
  57 int
  58 idspace_destroy(idspace_t idspace)
  59 {
  60         struct idspace *spc = idspace;
  61
  62         if (!spc)
  63                 return -EINVAL;
  64
  65         kmem_free_pages(spc->bitmap, calc_order(spc));
  66         kmem_free(spc);
  67
  68         return 0;
  69 }
  70
  71 int
  72 idspace_alloc_id(idspace_t idspace, id_t request, id_t *id)
  73 {
  74         struct idspace *spc = idspace;
  75         unsigned int bit;
  76
  77         if (!spc)
  78                 return -EINVAL;
  79
  80         if ((request != ANY_ID) &&
  81             ((request < spc->min_id) || (request > spc->max_id)))
  82                 return -EINVAL;
  83
  84         if (spc->size == spc->ids_in_use)
  85                 return -ENOENT;
  86
  87         if (request == ANY_ID) {
  88                 /* Allocate any available id */
  89                 bit = find_next_zero_bit(spc->bitmap, spc->size, spc->offset);
  90                 /* Handle wrap-around */
  91                 if (bit == spc->size)
  92                         bit = find_next_zero_bit(spc->bitmap, spc->offset, 0);
  93                 /* Next time start looking at the next id */
  94                 spc->offset = bit + 1;
  95                 if (spc->offset == spc->size)
  96                         spc->offset = 0;
  97         } else {
  98                 /* Allocate a specific ID */
  99                 bit = request - spc->min_id;
 100         }
 101
 102         if (test_and_set_bit(bit, spc->bitmap))
 103                 return -EBUSY;
 104
 105         ++spc->ids_in_use;
 106         if (id)
 107                 *id = bit + spc->min_id;
 108
 109         return 0;
 110 }
 111
 112 int
 113 idspace_free_id(idspace_t idspace, id_t id)
 114 {
 115         struct idspace *spc = idspace;
 116         unsigned int bit;
 117
 118         if (!spc)
 119                 return -EINVAL;
 120
 121         if ((id == ANY_ID) || (id < spc->min_id) || (id > spc->max_id))
 122                 return -EINVAL;
 123
 124         bit = id - spc->min_id;
 125         if (test_and_clear_bit(bit, spc->bitmap) == 0)
 126                 return -ENOENT;
 127
 128         --spc->ids_in_use;
 129
 130         return 0;
 131 }