ofproto/ofproto-dpif-rid.c

   1 /*
   2  * Copyright (c) 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "hmap.h"
  20 #include "hash.h"
  21 #include "ovs-thread.h"
  22 #include "ofproto-dpif-rid.h"
  23
  24 struct rid_map {
  25     struct hmap map;
  26 };
  27
  28 struct rid_node {
  29     struct hmap_node node;
  30     uint32_t recirc_id;
  31 };
  32
  33 struct rid_pool {
  34     struct rid_map ridmap;
  35     uint32_t base;         /* IDs in the range of [base, base + n_ids). */
  36     uint32_t n_ids;        /* Total number of ids in the pool. */
  37     uint32_t next_free_id; /* Possible next free id. */
  38 };
  39
  40 struct recirc_id_pool {
  41     struct ovs_mutex lock;
  42     struct rid_pool rids;
  43 };
  44
  45 #define RECIRC_ID_BASE  300
  46 #define RECIRC_ID_N_IDS  1024
  47
  48 static void rid_pool_init(struct rid_pool *rids,
  49                          uint32_t base, uint32_t n_ids);
  50 static void rid_pool_uninit(struct rid_pool *pool);
  51 static uint32_t rid_pool_alloc_id(struct rid_pool *pool);
  52 static void rid_pool_free_id(struct rid_pool *rids, uint32_t rid);
  53 static struct rid_node *rid_pool_find(struct rid_pool *rids, uint32_t id);
  54 static struct rid_node *rid_pool_add(struct rid_pool *rids, uint32_t id);
  55
  56 struct recirc_id_pool *
  57 recirc_id_pool_create(void)
  58 {
  59     struct recirc_id_pool *pool;
  60
  61     pool = xmalloc(sizeof *pool);
  62     rid_pool_init(&pool->rids, RECIRC_ID_BASE, RECIRC_ID_N_IDS);
  63     ovs_mutex_init(&pool->lock);
  64
  65     return pool;
  66 }
  67
  68 void
  69 recirc_id_pool_destroy(struct recirc_id_pool *pool)
  70 {
  71     rid_pool_uninit(&pool->rids);
  72     ovs_mutex_destroy(&pool->lock);
  73     free(pool);
  74 }
  75
  76 uint32_t
  77 recirc_id_alloc(struct recirc_id_pool *pool)
  78 {
  79     uint32_t id;
  80
  81     ovs_mutex_lock(&pool->lock);
  82     id = rid_pool_alloc_id(&pool->rids);
  83     ovs_mutex_unlock(&pool->lock);
  84
  85     return id;
  86 }
  87
  88 void
  89 recirc_id_free(struct recirc_id_pool *pool, uint32_t id)
  90 {
  91     ovs_mutex_lock(&pool->lock);
  92     rid_pool_free_id(&pool->rids, id);
  93     ovs_mutex_unlock(&pool->lock);
  94 }
  95
  96 static void
  97 rid_pool_init(struct rid_pool *rids, uint32_t base, uint32_t n_ids)
  98 {
  99     rids->base = base;
 100     rids->n_ids = n_ids;
 101     rids->next_free_id = base;
 102     hmap_init(&rids->ridmap.map);
 103 }
 104
 105 static void
 106 rid_pool_uninit(struct rid_pool *rids)
 107 {
 108     struct rid_node *rid, *next;
 109
 110     HMAP_FOR_EACH_SAFE(rid, next, node, &rids->ridmap.map) {
 111         hmap_remove(&rids->ridmap.map, &rid->node);
 112         free(rid);
 113     }
 114
 115     hmap_destroy(&rids->ridmap.map);
 116 }
 117
 118 static struct rid_node *
 119 rid_pool_find(struct rid_pool *rids, uint32_t id)
 120 {
 121     size_t hash;
 122     struct rid_node *rid;
 123
 124     hash = hash_int(id, 0);
 125     HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &rids->ridmap.map) {
 126         if (id == rid->recirc_id) {
 127             return rid;
 128         }
 129     }
 130     return NULL;
 131 }
 132
 133 static struct rid_node *
 134 rid_pool_add(struct rid_pool *rids, uint32_t id)
 135 {
 136     struct rid_node *rid = xmalloc(sizeof *rid);
 137     size_t hash;
 138
 139     rid->recirc_id = id;
 140     hash = hash_int(id, 0);
 141     hmap_insert(&rids->ridmap.map, &rid->node, hash);
 142     return rid;
 143 }
 144
 145 static uint32_t
 146 rid_pool_alloc_id(struct rid_pool *rids)
 147 {
 148     uint32_t id;
 149
 150     if (rids->n_ids == 0) {
 151         return 0;
 152     }
 153
 154     if (!(rid_pool_find(rids, rids->next_free_id))) {
 155         id = rids->next_free_id;
 156         goto found_free_id;
 157     }
 158
 159     for(id = rids->base; id < rids->base + rids->n_ids; id++) {
 160         if (rid_pool_find(rids, id)) {
 161             goto found_free_id;
 162         }
 163     }
 164
 165     /* Not available. */
 166     return 0;
 167
 168 found_free_id:
 169     rid_pool_add(rids, id);
 170
 171     if (id < rids->base + rids->n_ids) {
 172         rids->next_free_id = id + 1;
 173     } else {
 174         rids->next_free_id = rids->base;
 175     }
 176
 177     return id;
 178 }
 179
 180 static void
 181 rid_pool_free_id(struct rid_pool *rids, uint32_t id)
 182 {
 183     struct rid_node *rid;
 184     if (id > rids->base && (id <= rids->base + rids->n_ids)) {
 185         rid = rid_pool_find(rids, id);
 186         if (rid) {
 187             hmap_remove(&rids->ridmap.map, &rid->node);
 188         }
 189     }
 190 }