net: update licence for network headers
[dpdk.git] / lib / librte_hash / rte_fbk_hash.c
1 /**
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
11  *     * Redistributions of source code must retain the above copyright
12  *       notice, this list of conditions and the following disclaimer.
13  *     * Redistributions in binary form must reproduce the above copyright
14  *       notice, this list of conditions and the following disclaimer in
15  *       the documentation and/or other materials provided with the
16  *       distribution.
17  *     * Neither the name of Intel Corporation nor the names of its
18  *       contributors may be used to endorse or promote products derived
19  *       from this software without specific prior written permission.
20  *
21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 #include <stdint.h>
35 #include <stdio.h>
36 #include <stdarg.h>
37 #include <string.h>
38 #include <errno.h>
39
40 #include <sys/queue.h>
41 #include <rte_memory.h>
42 #include <rte_eal.h>
43 #include <rte_eal_memconfig.h>
44 #include <rte_malloc.h>
45 #include <rte_common.h>
46 #include <rte_per_lcore.h>
47 #include <rte_errno.h>
48 #include <rte_string_fns.h>
49 #include <rte_cpuflags.h>
50 #include <rte_log.h>
51 #include <rte_spinlock.h>
52
53 #include "rte_fbk_hash.h"
54
55 TAILQ_HEAD(rte_fbk_hash_list, rte_tailq_entry);
56
57 static struct rte_tailq_elem rte_fbk_hash_tailq = {
58         .name = "RTE_FBK_HASH",
59 };
60 EAL_REGISTER_TAILQ(rte_fbk_hash_tailq)
61
62 /**
63  * Performs a lookup for an existing hash table, and returns a pointer to
64  * the table if found.
65  *
66  * @param name
67  *   Name of the hash table to find
68  *
69  * @return
70  *   pointer to hash table structure or NULL on error.
71  */
72 struct rte_fbk_hash_table *
73 rte_fbk_hash_find_existing(const char *name)
74 {
75         struct rte_fbk_hash_table *h = NULL;
76         struct rte_tailq_entry *te;
77         struct rte_fbk_hash_list *fbk_hash_list;
78
79         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
80                                        rte_fbk_hash_list);
81
82         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
83         TAILQ_FOREACH(te, fbk_hash_list, next) {
84                 h = (struct rte_fbk_hash_table *) te->data;
85                 if (strncmp(name, h->name, RTE_FBK_HASH_NAMESIZE) == 0)
86                         break;
87         }
88         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
89         if (te == NULL) {
90                 rte_errno = ENOENT;
91                 return NULL;
92         }
93         return h;
94 }
95
96 /**
97  * Create a new hash table for use with four byte keys.
98  *
99  * @param params
100  *   Parameters used in creation of hash table.
101  *
102  * @return
103  *   Pointer to hash table structure that is used in future hash table
104  *   operations, or NULL on error.
105  */
106 struct rte_fbk_hash_table *
107 rte_fbk_hash_create(const struct rte_fbk_hash_params *params)
108 {
109         struct rte_fbk_hash_table *ht = NULL;
110         struct rte_tailq_entry *te;
111         char hash_name[RTE_FBK_HASH_NAMESIZE];
112         const uint32_t mem_size =
113                         sizeof(*ht) + (sizeof(ht->t[0]) * params->entries);
114         uint32_t i;
115         struct rte_fbk_hash_list *fbk_hash_list;
116
117         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
118                                        rte_fbk_hash_list);
119
120         /* Error checking of parameters. */
121         if ((!rte_is_power_of_2(params->entries)) ||
122                         (!rte_is_power_of_2(params->entries_per_bucket)) ||
123                         (params->entries == 0) ||
124                         (params->entries_per_bucket == 0) ||
125                         (params->entries_per_bucket > params->entries) ||
126                         (params->entries > RTE_FBK_HASH_ENTRIES_MAX) ||
127                         (params->entries_per_bucket > RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX)){
128                 rte_errno = EINVAL;
129                 return NULL;
130         }
131
132         snprintf(hash_name, sizeof(hash_name), "FBK_%s", params->name);
133
134         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
135
136         /* guarantee there's no existing */
137         TAILQ_FOREACH(te, fbk_hash_list, next) {
138                 ht = (struct rte_fbk_hash_table *) te->data;
139                 if (strncmp(params->name, ht->name, RTE_FBK_HASH_NAMESIZE) == 0)
140                         break;
141         }
142         ht = NULL;
143         if (te != NULL) {
144                 rte_errno = EEXIST;
145                 goto exit;
146         }
147
148         te = rte_zmalloc("FBK_HASH_TAILQ_ENTRY", sizeof(*te), 0);
149         if (te == NULL) {
150                 RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n");
151                 goto exit;
152         }
153
154         /* Allocate memory for table. */
155         ht = (struct rte_fbk_hash_table *)rte_zmalloc_socket(hash_name, mem_size,
156                         0, params->socket_id);
157         if (ht == NULL) {
158                 RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n");
159                 rte_free(te);
160                 goto exit;
161         }
162
163         /* Set up hash table context. */
164         snprintf(ht->name, sizeof(ht->name), "%s", params->name);
165         ht->entries = params->entries;
166         ht->entries_per_bucket = params->entries_per_bucket;
167         ht->used_entries = 0;
168         ht->bucket_mask = (params->entries / params->entries_per_bucket) - 1;
169         for (ht->bucket_shift = 0, i = 1;
170             (params->entries_per_bucket & i) == 0;
171             ht->bucket_shift++, i <<= 1)
172                 ; /* empty loop body */
173
174         if (params->hash_func != NULL) {
175                 ht->hash_func = params->hash_func;
176                 ht->init_val = params->init_val;
177         }
178         else {
179                 ht->hash_func = RTE_FBK_HASH_FUNC_DEFAULT;
180                 ht->init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT;
181         }
182
183         te->data = (void *) ht;
184
185         TAILQ_INSERT_TAIL(fbk_hash_list, te, next);
186
187 exit:
188         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
189
190         return ht;
191 }
192
193 /**
194  * Free all memory used by a hash table.
195  *
196  * @param ht
197  *   Hash table to deallocate.
198  */
199 void
200 rte_fbk_hash_free(struct rte_fbk_hash_table *ht)
201 {
202         struct rte_tailq_entry *te;
203         struct rte_fbk_hash_list *fbk_hash_list;
204
205         if (ht == NULL)
206                 return;
207
208         fbk_hash_list = RTE_TAILQ_CAST(rte_fbk_hash_tailq.head,
209                                        rte_fbk_hash_list);
210
211         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
212
213         /* find out tailq entry */
214         TAILQ_FOREACH(te, fbk_hash_list, next) {
215                 if (te->data == (void *) ht)
216                         break;
217         }
218
219         if (te == NULL) {
220                 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
221                 return;
222         }
223
224         TAILQ_REMOVE(fbk_hash_list, te, next);
225
226         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
227
228         rte_free(ht);
229         rte_free(te);
230 }