source: trunk/kernel/kern/keysdb.c @ 1

Last change on this file since 1 was 1, checked in by alain, 5 years ago

First import

File size: 6.0 KB
Line 
1/*
2 * keysdb.c - fixed radix-cache implementation
3 *
4 * Copyright (c) 2008,2009,2010,2011,2012 Ghassan Almaless
5 * Copyright (c) 2011,2012 UPMC Sorbonne Universites
6 *
7 * This file is part of ALMOS-kernel.
8 *
9 * ALMOS-kernel is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; version 2.0 of the License.
12 *
13 * ALMOS-kernel is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23#include <errno.h>
24#include <libk.h>
25#include <kdmsg.h>
26#include <bits.h>
27#include <page.h>
28#include <ppm.h>
29#include <pmm.h>
30#include <thread.h>
31#include <task.h>
32#include <kmem.h>
33#include <keysdb.h>
34
35#define KEYS_PER_REC_LOG2   6
36
37////////////////////////////////////
38error_t keysdb_init( keysdb_t * db )
39                     uint32_t   key_width )
40{
41        page_t     * page;
42        kmem_req_t   req;
43 
44        db->records_nr   = CONFIG_PMM_PAGE_SIZE / sizeof(keys_record_t*);
45        db->records_bits = bits_log2(db->records_nr);
46
47    db->keys_nr      = KEYS_PER_RECORD;
48    db->keys_bits    = bits_log2( db->keys_nr );
49
50    // allocates one single page
51        req.type  = KMEM_PAGE;
52        req.size  = 0;
53        req.flags = AF_USER | AF_ZERO;
54        page = kmem_alloc(&req);
55        if(page == NULL) return ENOMEM;
56 
57        db->root = ppm_page2addr( page );
58        db->page = page;
59
60        return 0;
61}
62
63///////////////////////////////////////
64void keysdb_destroy( keysdb_t * db )
65{
66        kmem_req_t req;
67        uint32_t   i;
68
69        req.type = KMEM_KEYSREC;
70
71        for( i=0 ; i < db->records_nr ; i++ )
72        {
73                if(db->root[i] == NULL) continue;
74
75                req.ptr = db->root[i];
76                kmem_free(&req);
77        }
78
79        req.type = KMEM_PAGE;
80        req.ptr = db->page;
81        kmem_free(&req);
82}
83
84//////////////////////////////////
85void keysdb_print( keysdb_t * db,
86                   char     * name )
87{
88        uint32_t        i; 
89        uint32_t        j;
90    keys_record_t * rec;
91 
92        printk(INFO, "%s / keys_per_record = %d / records = %d\n", 
93           name, db->keys_nr , db->records_nr );
94
95        for( i=0 ; i < db->records_nr; i++ )
96        {
97        rec = db_root[i];   
98                if( rec == NULL ) continue;
99   
100            printk(INFO, "record[%d] @ = 0x%x] [", index , rec );
101            for( j=0; j < db->keys_nr ; i++) printk(INFO, "  val[%d] = %x\n", j , rec->tbl[j]);
102        }
103}
104
105/////////////////////////////////////
106error_t keysdb_insert( keysdb_t * db,
107                       uint32_t   key,
108                       void     * value )
109{
110    // Check key
111    if( key >> (db->keys_bits + db->records_bits) ) return EINVAL;
112
113    // compute indexes
114    uint32_t        bits      = db->keys_bits;
115        uint32_t        rec_index = key >> bits;              // index in records table
116        uint32_t        key_index = key & ((1 << bits) - 1);  // index in record
117
118        kmem_req_t      req;        // kmem request for new record
119        keys_record_t * rec;        // pointer on selected record
120        bool_t          isAtomic;
121
122    // get address of pointer on the selected record in first level table.
123    // it can be NULL if the selected record has not be allocated yet.
124        volatile keys_record_t ** recptr = &db->root[record_index];
125
126    // we must allocate memory for the selected record if record pointer is NULL,
127    // and atomically update the records table with the new record pointer.
128        while( *recptr == NULL )
129        {
130        // allocate memory for record
131        req.type = KMEM_KEYSREC;
132        req.size = sizeof(keys_record_t);
133        req.flags = AF_USER | AF_ZERO;
134        rec = kmem_alloc(&req);
135        if( rec == NULL) return ENOMEM;
136
137        // try to update records array
138                isAtomic = cpu_atomic_cas( &db->root[record_index] , 0 , (uint32_t)rec );
139
140        // release record memory if not atomic
141        if( isAtomic == false )
142            {
143                    req.ptr = rec;
144                    kmem_free(&req);
145            }
146        }
147
148    // get pointer on selected record.
149        rec = db->root[record_index];
150
151    // check selected slot empty in selected record
152        if(rec->tbl[key_index] != NULL) return EEXIST;
153
154    // register the value
155        rec->tbl[key_index] = value;
156
157        return 0;
158}
159
160////////////////////////////////////
161void * keysdb_remove( keysdb_t * db,
162                      uint32_t   key )
163{
164    // compute indexes
165    uint32_t        bits      = db->keys_bits;
166        uint32_t        rec_index = key >> bits;              // index in records table
167        uint32_t        key_index = key & ((1 << bits) - 1);  // index in record
168 
169    // get record pointer
170        keys_record_t * rec = db->root[record_index];
171 
172        if(rec == NULL) return NULL;
173
174    // get value
175        void * value = rec->tbl[key_index];
176
177    // reset selected slot
178        rec->tbl[key_index] = NULL;
179        cpu_wbflush();
180
181        return value;
182}
183
184////////////////////////////////////
185void * keysdb_lookup( keysdb_t * db,
186                      uint32_t   key )
187{
188    // compute indexes
189    uint32_t        bits      = db->keys_bits;
190        uint32_t        rec_index = key >> db->keys_bits;
191        uint32_t        key_index = key & ((1 << bits) - 1);
192
193    // get record pointer
194        keys_record_t * recptr = db->root[rec_index]; 
195
196    // compute value
197        void * value = (recptr == NULL) ? NULL : recptr->tbl[key_index];
198
199        return value;
200}
201
202
203/*
204///////////////////////////////////
205error_t keysdb_bind( keysdb_t * db,
206                     uint32_t   key_start,
207                     uint32_t   keys_nr,
208                     void     * value )
209{
210        error_t err;
211        uint32_t i;
212
213        err = 0;
214
215        for(i = 0; i < keys_nr; i++)
216        {
217                err = keysdb_insert(db, key_start + i, value);
218                if(err != 0) break;
219        }
220
221        while((err != 0) && (i != 0))
222        {
223                i--;
224                keysdb_remove(db, key_start + i);
225        }
226
227        return err;
228}
229
230/////////////////////////////////////
231error_t keysdb_unbind( keysdb_t * db,
232                       uint32_t   key_start,
233                       uint32_t   keys_nr )
234{
235        uint32_t i;
236
237        for(i = 0; i < keys_nr; i++)
238                (void)keysdb_remove(db , key_start + i);
239
240        return 0;
241}
242
243*/
Note: See TracBrowser for help on using the repository browser.