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

/*
 * keysdb.c - fixed radix-cache implementation
 * 
 * Copyright (c) 2008,2009,2010,2011,2012 Ghassan Almaless
 * Copyright (c) 2011,2012 UPMC Sorbonne Universites
 * 
 * This file is part of ALMOS-kernel.
 *
 * ALMOS-kernel is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-kernel is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <errno.h>
#include <libk.h>
#include <kdmsg.h>
#include <bits.h>
#include <page.h>
#include <ppm.h>
#include <pmm.h>
#include <thread.h>
#include <task.h>
#include <kmem.h>
#include <keysdb.h>

#define KEYS_PER_REC_LOG2   6

////////////////////////////////////
error_t keysdb_init( keysdb_t * db )
                     uint32_t   key_width )
{
        page_t     * page;
        kmem_req_t   req;
  
        db->records_nr   = CONFIG_PMM_PAGE_SIZE / sizeof(keys_record_t*);
        db->records_bits = bits_log2(db->records_nr);

    db->keys_nr      = KEYS_PER_RECORD;
    db->keys_bits    = bits_log2( db->keys_nr );

    // allocates one single page
        req.type  = KMEM_PAGE;
        req.size  = 0;
        req.flags = AF_USER | AF_ZERO;
        page = kmem_alloc(&req);
        if(page == NULL) return ENOMEM;
  
        db->root = ppm_page2addr( page );
        db->page = page;

        return 0;
}

///////////////////////////////////////
void keysdb_destroy( keysdb_t * db )
{
        kmem_req_t req;
        uint32_t   i;

        req.type = KMEM_KEYSREC;

        for( i=0 ; i < db->records_nr ; i++ )
        {
                if(db->root[i] == NULL) continue;

                req.ptr = db->root[i];
                kmem_free(&req);
        }

        req.type = KMEM_PAGE;
        req.ptr = db->page;
        kmem_free(&req);
}

//////////////////////////////////
void keysdb_print( keysdb_t * db,
                   char     * name )
{
        uint32_t        i;  
        uint32_t        j;
    keys_record_t * rec;
 
        printk(INFO, "%s / keys_per_record = %d / records = %d\n", 
           name, db->keys_nr , db->records_nr );

        for( i=0 ; i < db->records_nr; i++ )
        {
        rec = db_root[i];   
                if( rec == NULL ) continue;
    
            printk(INFO, "record[%d] @ = 0x%x] [", index , rec );
            for( j=0; j < db->keys_nr ; i++) printk(INFO, "  val[%d] = %x\n", j , rec->tbl[j]);
        }
}

/////////////////////////////////////
error_t keysdb_insert( keysdb_t * db,
                       uint32_t   key,
                       void     * value )
{
    // Check key 
    if( key >> (db->keys_bits + db->records_bits) ) return EINVAL;

    // compute indexes
    uint32_t        bits      = db->keys_bits;
        uint32_t        rec_index = key >> bits;              // index in records table
        uint32_t        key_index = key & ((1 << bits) - 1);  // index in record

        kmem_req_t      req;        // kmem request for new record
        keys_record_t * rec;        // pointer on selected record
        bool_t          isAtomic;

    // get address of pointer on the selected record in first level table.
    // it can be NULL if the selected record has not be allocated yet.
        volatile keys_record_t ** recptr = &db->root[record_index];

    // we must allocate memory for the selected record if record pointer is NULL,
    // and atomically update the records table with the new record pointer.
        while( *recptr == NULL )
        {
        // allocate memory for record
        req.type = KMEM_KEYSREC;
        req.size = sizeof(keys_record_t);
        req.flags = AF_USER | AF_ZERO;
        rec = kmem_alloc(&req);
        if( rec == NULL) return ENOMEM;

        // try to update records array
                isAtomic = cpu_atomic_cas( &db->root[record_index] , 0 , (uint32_t)rec );

        // release record memory if not atomic
        if( isAtomic == false )
            {
                    req.ptr = rec;
                    kmem_free(&req);
            }
        }

    // get pointer on selected record.
        rec = db->root[record_index];

    // check selected slot empty in selected record
        if(rec->tbl[key_index] != NULL) return EEXIST;

    // register the value
        rec->tbl[key_index] = value;

        return 0;
}

////////////////////////////////////
void * keysdb_remove( keysdb_t * db,
                      uint32_t   key )
{
    // compute indexes
    uint32_t        bits      = db->keys_bits;
        uint32_t        rec_index = key >> bits;              // index in records table
        uint32_t        key_index = key & ((1 << bits) - 1);  // index in record
  
    // get record pointer
        keys_record_t * rec = db->root[record_index];
 
        if(rec == NULL) return NULL;

    // get value
        void * value = rec->tbl[key_index];

    // reset selected slot
        rec->tbl[key_index] = NULL;
        cpu_wbflush();

        return value;
}

////////////////////////////////////
void * keysdb_lookup( keysdb_t * db,
                      uint32_t   key )
{
    // compute indexes
    uint32_t        bits      = db->keys_bits;
        uint32_t        rec_index = key >> db->keys_bits;
        uint32_t        key_index = key & ((1 << bits) - 1);

    // get record pointer
        keys_record_t * recptr = db->root[rec_index]; 

    // compute value
        void * value = (recptr == NULL) ? NULL : recptr->tbl[key_index];

        return value;
}


/*
///////////////////////////////////
error_t keysdb_bind( keysdb_t * db,
                     uint32_t   key_start, 
                     uint32_t   keys_nr,
                     void     * value )
{
        error_t err;
        uint32_t i;

        err = 0;

        for(i = 0; i < keys_nr; i++)
        {
                err = keysdb_insert(db, key_start + i, value);
                if(err != 0) break;
        }

        while((err != 0) && (i != 0))
        {
                i--;
                keysdb_remove(db, key_start + i);
        }

        return err;
}

/////////////////////////////////////
error_t keysdb_unbind( keysdb_t * db,
                       uint32_t   key_start,
                       uint32_t   keys_nr )
{
        uint32_t i;

        for(i = 0; i < keys_nr; i++)
                (void)keysdb_remove(db , key_start + i);

        return 0;
}

*/