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