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_node {
  25     struct hmap_node node;
  26     uint32_t recirc_id;
  27 };
  28
  29 struct rid_pool {
  30     struct hmap map;
  31     uint32_t base;         /* IDs in the range of [base, base + n_ids). */
  32     uint32_t n_ids;        /* Total number of ids in the pool. */
  33     uint32_t next_free_id; /* Possible next free id. */
  34 };
  35
  36 struct recirc_id_pool {
  37     struct ovs_mutex lock;
  38     struct rid_pool rids;
  39 };
  40
  41 #define RECIRC_ID_BASE  300
  42 #define RECIRC_ID_N_IDS  1024
  43
  44 static void rid_pool_init(struct rid_pool *rids,
  45                          uint32_t base, uint32_t n_ids);
  46 static void rid_pool_uninit(struct rid_pool *pool);
  47 static uint32_t rid_pool_alloc_id(struct rid_pool *pool);
  48 static void rid_pool_free_id(struct rid_pool *rids, uint32_t rid);
  49 static struct rid_node *rid_pool_find(struct rid_pool *rids, uint32_t id);
  50 static void rid_pool_add(struct rid_pool *rids, uint32_t id);
  51
  52 struct recirc_id_pool *
  53 recirc_id_pool_create(void)
  54 {
  55     struct recirc_id_pool *pool;
  56
  57     pool = xmalloc(sizeof *pool);
  58     rid_pool_init(&pool->rids, RECIRC_ID_BASE, RECIRC_ID_N_IDS);
  59     ovs_mutex_init(&pool->lock);
  60
  61     return pool;
  62 }
  63
  64 void
  65 recirc_id_pool_destroy(struct recirc_id_pool *pool)
  66 {
  67     rid_pool_uninit(&pool->rids);
  68     ovs_mutex_destroy(&pool->lock);
  69     free(pool);
  70 }
  71
  72 uint32_t
  73 recirc_id_alloc(struct recirc_id_pool *pool)
  74 {
  75     uint32_t id;
  76
  77     ovs_mutex_lock(&pool->lock);
  78     id = rid_pool_alloc_id(&pool->rids);
  79     ovs_mutex_unlock(&pool->lock);
  80
  81     return id;
  82 }
  83
  84 void
  85 recirc_id_free(struct recirc_id_pool *pool, uint32_t id)
  86 {
  87     ovs_mutex_lock(&pool->lock);
  88     rid_pool_free_id(&pool->rids, id);
  89     ovs_mutex_unlock(&pool->lock);
  90 }
  91
  92 static void
  93 rid_pool_init(struct rid_pool *rids, uint32_t base, uint32_t n_ids)
  94 {
  95     rids->base = base;
  96     rids->n_ids = n_ids;
  97     rids->next_free_id = base;
  98     hmap_init(&rids->map);
  99 }
 100
 101 static void
 102 rid_pool_uninit(struct rid_pool *rids)
 103 {
 104     struct rid_node *rid, *next;
 105
 106     HMAP_FOR_EACH_SAFE(rid, next, node, &rids->map) {
 107         hmap_remove(&rids->map, &rid->node);
 108         free(rid);
 109     }
 110
 111     hmap_destroy(&rids->map);
 112 }
 113
 114 static struct rid_node *
 115 rid_pool_find(struct rid_pool *rids, uint32_t id)
 116 {
 117     size_t hash;
 118     struct rid_node *rid;
 119
 120     hash = hash_int(id, 0);
 121     HMAP_FOR_EACH_WITH_HASH(rid, node, hash, &rids->map) {
 122         if (id == rid->recirc_id) {
 123             return rid;
 124         }
 125     }
 126     return NULL;
 127 }
 128
 129 static void
 130 rid_pool_add(struct rid_pool *rids, uint32_t id)
 131 {
 132     struct rid_node *rid = xmalloc(sizeof *rid);
 133     size_t hash;
 134
 135     rid->recirc_id = id;
 136     hash = hash_int(id, 0);
 137     hmap_insert(&rids->map, &rid->node, hash);
 138 }
 139
 140 static uint32_t
 141 rid_pool_alloc_id(struct rid_pool *rids)
 142 {
 143     uint32_t id;
 144
 145     if (rids->n_ids == 0) {
 146         return 0;
 147     }
 148
 149     if (!(rid_pool_find(rids, rids->next_free_id))) {
 150         id = rids->next_free_id;
 151         goto found_free_id;
 152     }
 153
 154     for(id = rids->base; id < rids->base + rids->n_ids; id++) {
 155         if (!rid_pool_find(rids, id)) {
 156             goto found_free_id;
 157         }
 158     }
 159
 160     /* Not available. */
 161     return 0;
 162
 163 found_free_id:
 164     rid_pool_add(rids, id);
 165
 166     if (id < rids->base + rids->n_ids) {
 167         rids->next_free_id = id + 1;
 168     } else {
 169         rids->next_free_id = rids->base;
 170     }
 171
 172     return id;
 173 }
 174
 175 static void
 176 rid_pool_free_id(struct rid_pool *rids, uint32_t id)
 177 {
 178     struct rid_node *rid;
 179     if (id > rids->base && (id <= rids->base + rids->n_ids)) {
 180         rid = rid_pool_find(rids, id);
 181         if (rid) {
 182             hmap_remove(&rids->map, &rid->node);
 183         }
 184     }
 185 }