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 }
  74
  75 uint32_t
  76 recirc_id_alloc(struct recirc_id_pool *pool)
  77 {
  78     uint32_t id;
  79
  80     ovs_mutex_lock(&pool->lock);
  81     id = rid_pool_alloc_id(&pool->rids);
  82     ovs_mutex_unlock(&pool->lock);
  83
  84     return id;
  85 }
  86
  87 void
  88 recirc_id_free(struct recirc_id_pool *pool, uint32_t id)
  89 {
  90     ovs_mutex_lock(&pool->lock);
  91     rid_pool_free_id(&pool->rids, id);
  92     ovs_mutex_unlock(&pool->lock);
  93 }
  94
  95 static void
  96 rid_pool_init(struct rid_pool *rids, uint32_t base, uint32_t n_ids)
  97 {
  98     rids->base = base;
  99     rids->n_ids = n_ids;
 100     rids->next_free_id = base;
 101     hmap_init(&rids->ridmap.map);
 102 }
 103
 104 static void
 105 rid_pool_uninit(struct rid_pool *rids)
 106 {
 107     struct rid_node *rid, *next;
 108
 109     HMAP_FOR_EACH_SAFE(rid, next, node, &rids->ridmap.map) {
 110         hmap_remove(&rids->ridmap.map, &rid->node);
 111         free(rid);
 112     }
 113
 114     hmap_destroy(&rids->ridmap.map);
 115 }
 116
 117 static struct rid_node *
 118 rid_pool_find(struct rid_pool *rids, uint32_t id)
 119 {
 120     size_t hash;
 121     struct rid_node *rid;
 122
 123     hash = hash_int(id, 0);
 124     HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &rids->ridmap.map) {
 125         if (id == rid->recirc_id) {
 126             return rid;
 127         }
 128     }
 129     return NULL;
 130 }
 131
 132 static struct rid_node *
 133 rid_pool_add(struct rid_pool *rids, uint32_t id)
 134 {
 135     struct rid_node *rid = xmalloc(sizeof *rid);
 136     size_t hash;
 137
 138     rid->recirc_id = id;
 139     hash = hash_int(id, 0);
 140     hmap_insert(&rids->ridmap.map, &rid->node, hash);
 141     return rid;
 142 }
 143
 144 static uint32_t
 145 rid_pool_alloc_id(struct rid_pool *rids)
 146 {
 147     uint32_t id;
 148
 149     if (rids->n_ids == 0) {
 150         return 0;
 151     }
 152
 153     if (!(rid_pool_find(rids, rids->next_free_id))) {
 154         id = rids->next_free_id;
 155         goto found_free_id;
 156     }
 157
 158     for(id = rids->base; id < rids->base + rids->n_ids; id++) {
 159         if (rid_pool_find(rids, id)) {
 160             goto found_free_id;
 161         }
 162     }
 163
 164     /* Not available. */
 165     return 0;
 166
 167 found_free_id:
 168     rid_pool_add(rids, id);
 169
 170     if (id < rids->base + rids->n_ids) {
 171         rids->next_free_id = id + 1;
 172     } else {
 173         rids->next_free_id = rids->base;
 174     }
 175
 176     return id;
 177 }
 178
 179 static void
 180 rid_pool_free_id(struct rid_pool *rids, uint32_t id)
 181 {
 182     struct rid_node *rid;
 183     if (id > rids->base && (id <= rids->base + rids->n_ids)) {
 184         rid = rid_pool_find(rids, id);
 185         if (rid) {
 186             hmap_remove(&rids->ridmap.map, &rid->node);
 187         }
 188     }
 189 }