Line data    Source code

       1             : /*
       2             :  * vr_btable.c -- Big tables. With (kernel)malloc, there is a limitation of
       3             :  * how much contiguous memory we will get (4M). So, for allocations more than
       4             :  * 4M, we need a way to manage the requests, and that's where big tables come
       5             :  * in. Basically, a two level table.
       6             :  *
       7             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       8             :  * Copyright Contributors to the OpenSDN project
       9             :  */
      10             : #include <vr_os.h>
      11             : #include <vrouter.h>
      12             : #include "vr_btable.h"
      13             : 
      14             : /*
      15             :  * The aim of btable is to workaround kernel's limitation of 4M allocation
      16             :  * size by allocating multiple chunks of 4M for a huge allocation.
      17             :  *
      18             :  * In the linux world, while vmalloc can provide a huge chunk of memory,
      19             :  * kmalloc is preferred to vmalloc for the following reasons
      20             :  *
      21             :  * - lesser TLB misses
      22             :  * - vmalloc is restricted in 32 bit systems
      23             :  * - potential pagefaults
      24             :  *
      25             :  * Also, in 2.6, there are problems with mmap-ing k(mz)alloced memory (for
      26             :  * flow table). So, a page based allocation is what btable will follow.
      27             :  *
      28             :  * The basic oprations supported are alloc, free, and get. get is defined in
      29             :  * the header file as an inline function for performance reasons.
      30             :  */
      31             : 
      32             : /*
      33             :  * the discontiguous chunks of memory are seen as partitions, and hence the
      34             :  * nomenclature
      35             :  */
      36             : struct vr_btable_partition *
      37           0 : vr_btable_get_partition(struct vr_btable *table, unsigned int partition)
      38             : {
      39           0 :     if (partition >= table->vb_partitions)
      40           0 :         return NULL;
      41             : 
      42           0 :     return &table->vb_table_info[partition];
      43             : }
      44             : 
      45             : /*
      46             :  * given an offset into the total memory managed by the btable (i.e memory
      47             :  * across all partitions), return the corresponding virtual address
      48             :  */
      49             : void *
      50           0 : vr_btable_get_address(struct vr_btable *table, unsigned int offset)
      51             : {
      52             :     unsigned int i;
      53             :     struct vr_btable_partition *partition;
      54             : 
      55           0 :     for (i = 0; i < table->vb_partitions; i++) {
      56           0 :         partition = vr_btable_get_partition(table, i);
      57           0 :         if (!partition)
      58           0 :             break;
      59             : 
      60           0 :         if (offset >= partition->vb_offset &&
      61           0 :                 offset < partition->vb_offset + partition->vb_mem_size)
      62           0 :             return (char *)table->vb_mem[i] + (offset - partition->vb_offset);
      63             :     }
      64             : 
      65           0 :     return NULL;
      66             : }
      67             : 
      68             : void
      69         789 : vr_btable_free(struct vr_btable *table)
      70             : {
      71             :     unsigned int i;
      72             : 
      73         789 :     if (!table)
      74           0 :         return;
      75             : 
      76         789 :     if (!(table->vb_flags & VB_FLAG_MEMORY_ATTACHED) &&
      77         577 :             (table->vb_mem)) {
      78        1154 :         for (i = 0; i < table->vb_partitions; i++) {
      79         577 :             if (table->vb_mem[i]) {
      80         577 :                 vr_page_free(table->vb_mem[i],
      81         577 :                         table->vb_table_info[i].vb_mem_size);
      82             :             }
      83             :         }
      84             :     }
      85             : 
      86         789 :     vr_free(table, VR_BTABLE_OBJECT);
      87             : 
      88         789 :     return;
      89             : }
      90             : 
      91             : static void
      92         915 : vr_btable_fill_pow2_fields(struct vr_btable *table) {
      93         915 :     unsigned int number = table->vb_alloc_limit;
      94             : 
      95         915 :     if (!(table->vb_alloc_limit & (table->vb_alloc_limit - 1))) {
      96       18978 :         while (number >>= 1)
      97       18169 :             table->vb_alloc_limit_log++;
      98         809 :         table->vb_alloc_limit_mask = table->vb_alloc_limit - 1;
      99             :     } else {
     100         106 :         table->vb_alloc_limit_log = 0;
     101         106 :         table->vb_alloc_limit_mask = 0;
     102             :     }
     103         915 : }
     104             : 
     105             : struct vr_btable *
     106         703 : vr_btable_alloc(unsigned int num_entries, unsigned int entry_size)
     107             : {
     108         703 :     unsigned int i = 0, num_parts, remainder;
     109             :     unsigned int total_parts, alloc_size;
     110             :     uint64_t total_mem;
     111             :     struct vr_btable *table;
     112         703 :     unsigned int offset = 0;
     113             : 
     114         703 :     total_mem = num_entries * entry_size;
     115             : 
     116         703 :     num_parts = total_mem / VR_SINGLE_ALLOC_LIMIT;
     117         703 :     remainder = total_mem % VR_SINGLE_ALLOC_LIMIT;
     118             : 
     119         703 :     total_parts = num_parts;
     120             :     /*
     121             :      * anything left over that is not a multiple of VR_SINGLE_ALLOC_LIMIT
     122             :      * gets accomodated in the remainder, and hence an extra partition has
     123             :      * to be given
     124             :      */
     125         703 :     if (remainder)
     126         650 :         total_parts++;
     127             : 
     128         703 :     if (num_parts) {
     129             :         /*
     130             :          * the entry size has to be a factor of VR_SINGLE_ALLOC limit.
     131             :          * otherwise, we might access memory beyond the allocated chunk
     132             :          * while accessing the last entry
     133             :          */
     134          53 :         if (VR_SINGLE_ALLOC_LIMIT % entry_size)
     135           0 :             return NULL;
     136             :     }
     137             : 
     138         703 :     if (!total_parts)
     139           0 :         return NULL;
     140             : 
     141         703 :     alloc_size = sizeof(*table) + (total_parts * (sizeof(void *))) +
     142             :         (total_parts * sizeof(struct vr_btable_partition));
     143             : 
     144         703 :     table = vr_zalloc(alloc_size, VR_BTABLE_OBJECT);
     145         703 :     if (!table)
     146           0 :         return NULL;
     147             : 
     148         703 :     table->vb_alloc_limit = VR_SINGLE_ALLOC_LIMIT;
     149         703 :     table->vb_mem = (void **)(table + 1);
     150         703 :     table->vb_table_info =
     151         703 :         (struct vr_btable_partition *)((unsigned char *)table->vb_mem +
     152         703 :                 (total_parts * sizeof(void *)));
     153             : 
     154         703 :     if (num_parts) {
     155         106 :         for (i = 0; i < num_parts; i++) {
     156          53 :             table->vb_mem[i] = vr_page_alloc(VR_SINGLE_ALLOC_LIMIT);
     157          53 :             if (!table->vb_mem[i])
     158           0 :                 goto exit_alloc;
     159          53 :             table->vb_table_info[i].vb_mem_size = VR_SINGLE_ALLOC_LIMIT;
     160          53 :             table->vb_table_info[i].vb_offset = offset;
     161          53 :             offset += table->vb_table_info[i].vb_mem_size;
     162          53 :             table->vb_partitions++;
     163             :         }
     164             :     }
     165             : 
     166         703 :     if (remainder) {
     167         650 :         table->vb_mem[i] = vr_page_alloc(remainder);
     168         650 :         if (!table->vb_mem[i])
     169           0 :             goto exit_alloc;
     170         650 :         table->vb_table_info[i].vb_mem_size = remainder;
     171         650 :         table->vb_table_info[i].vb_offset = offset;
     172         650 :         table->vb_partitions++;
     173             :     }
     174             : 
     175         703 :     table->vb_entries = num_entries;
     176         703 :     table->vb_esize = entry_size;
     177             : 
     178         703 :     vr_btable_fill_pow2_fields(table);
     179             : 
     180         703 :     return table;
     181             : 
     182           0 : exit_alloc:
     183           0 :     vr_btable_free(table);
     184           0 :     return NULL;
     185             : }
     186             : 
     187             : struct vr_btable *
     188         212 : vr_btable_attach(struct iovec *iov, unsigned int iov_len,
     189             :         unsigned short esize)
     190             : {
     191             :     unsigned int i, alloc_size;
     192         212 :     unsigned int offset = 0, total_size = 0;
     193             :     struct vr_btable *table;
     194             : 
     195         212 :     if (!iov || !iov_len)
     196           0 :         return NULL;
     197             : 
     198         212 :     if (iov[0].iov_len % esize)
     199           0 :         return NULL;
     200             : 
     201         212 :     alloc_size = sizeof(struct vr_btable);
     202         212 :     alloc_size += (sizeof(void *) * iov_len);
     203         212 :     alloc_size += (sizeof(struct vr_btable_partition) * iov_len);
     204             : 
     205             : 
     206         212 :     table = (struct vr_btable *)vr_zalloc(alloc_size, VR_BTABLE_OBJECT);
     207         212 :     if (!table)
     208           0 :         return NULL;
     209             : 
     210         212 :     table->vb_esize = esize;
     211         212 :     table->vb_partitions = iov_len;
     212         212 :     table->vb_alloc_limit = iov->iov_len;
     213         212 :     table->vb_mem = (void **)(table + 1);
     214         212 :     table->vb_table_info =
     215         212 :         (struct vr_btable_partition *)((unsigned char *)table->vb_mem +
     216         212 :                 (iov_len * sizeof(void *)));
     217             : 
     218         424 :     for (i = 0; i < iov_len; i++) {
     219         212 :         table->vb_mem[i] = iov[i].iov_base;
     220         212 :         if ((iov[i].iov_len != table->vb_alloc_limit) &&
     221           0 :                 (i != (iov_len - 1)))
     222           0 :             goto error;
     223             : 
     224         212 :         table->vb_table_info[i].vb_mem_size = iov[i].iov_len;
     225         212 :         table->vb_table_info[i].vb_offset = offset;
     226             : 
     227         212 :         offset += iov[i].iov_len;
     228         212 :         total_size += iov[i].iov_len;
     229             :     }
     230             : 
     231         212 :     if (total_size % esize)
     232           0 :         goto error;
     233             : 
     234         212 :     table->vb_entries = (total_size / esize);
     235         212 :     table->vb_flags |= VB_FLAG_MEMORY_ATTACHED;
     236             : 
     237         212 :     vr_btable_fill_pow2_fields(table);
     238             : 
     239         212 :     return table;
     240             : 
     241           0 : error:
     242           0 :     vr_btable_free(table);
     243           0 :     return NULL;
     244             : }
     245             :