src/vppinfra/vec.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16   Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
  17
  18   Permission is hereby granted, free of charge, to any person obtaining
  19   a copy of this software and associated documentation files (the
  20   "Software"), to deal in the Software without restriction, including
  21   without limitation the rights to use, copy, modify, merge, publish,
  22   distribute, sublicense, and/or sell copies of the Software, and to
  23   permit persons to whom the Software is furnished to do so, subject to
  24   the following conditions:
  25
  26   The above copyright notice and this permission notice shall be
  27   included in all copies or substantial portions of the Software.
  28
  29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  36 */
  37
  38 #include <vppinfra/vec.h>
  39 #include <vppinfra/mem.h>
  40
  41 #ifndef CLIB_VECTOR_GROW_BY_ONE
  42 #define CLIB_VECTOR_GROW_BY_ONE 0
  43 #endif
  44
  45 /* Vector resize operator.  Called as needed by various macros such as
  46    vec_add1() when we need to allocate memory. */
  47 __clib_export void *
  48 vec_resize_allocate_memory (void *v,
  49                             word length_increment,
  50                             uword data_bytes,
  51                             uword header_bytes, uword data_align,
  52                             uword numa_id)
  53 {
  54   vec_header_t *vh = _vec_find (v);
  55   uword old_alloc_bytes, new_alloc_bytes;
  56   void *old, *new;
  57   void *oldheap;
  58
  59   header_bytes = vec_header_bytes (header_bytes);
  60
  61   data_bytes += header_bytes;
  62
  63   if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
  64     {
  65       oldheap = clib_mem_get_per_cpu_heap ();
  66       clib_mem_set_per_cpu_heap (clib_mem_get_per_numa_heap (numa_id));
  67     }
  68
  69   if (!v)
  70     {
  71       new = clib_mem_alloc_aligned_at_offset (data_bytes, data_align, header_bytes, 1   /* yes, call os_out_of_memory */
  72         );
  73       new_alloc_bytes = clib_mem_size (new);
  74       CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
  75       clib_memset (new, 0, new_alloc_bytes);
  76       CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
  77       v = new + header_bytes;
  78       _vec_len (v) = length_increment;
  79       _vec_numa (v) = numa_id;
  80       if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
  81         clib_mem_set_per_cpu_heap (oldheap);
  82       return v;
  83     }
  84
  85   vh->len += length_increment;
  86   old = v - header_bytes;
  87
  88   /* Vector header must start heap object. */
  89   ASSERT (clib_mem_is_heap_object (old));
  90
  91   old_alloc_bytes = clib_mem_size (old);
  92
  93   /* Need to resize? */
  94   if (data_bytes <= old_alloc_bytes)
  95     {
  96       CLIB_MEM_UNPOISON (v, data_bytes);
  97       if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
  98         clib_mem_set_per_cpu_heap (oldheap);
  99       return v;
 100     }
 101
 102 #if CLIB_VECTOR_GROW_BY_ONE > 0
 103   new_alloc_bytes = data_bytes;
 104 #else
 105   new_alloc_bytes = (old_alloc_bytes * 3) / 2;
 106   if (new_alloc_bytes < data_bytes)
 107     new_alloc_bytes = data_bytes;
 108 #endif
 109
 110   new =
 111     clib_mem_alloc_aligned_at_offset (new_alloc_bytes, data_align,
 112                                       header_bytes,
 113                                       1 /* yes, call os_out_of_memory */ );
 114
 115   /* FIXME fail gracefully. */
 116   if (!new)
 117     clib_panic
 118       ("vec_resize fails, length increment %d, data bytes %d, alignment %d",
 119        length_increment, data_bytes, data_align);
 120
 121   CLIB_MEM_UNPOISON (old, old_alloc_bytes);
 122   clib_memcpy_fast (new, old, old_alloc_bytes);
 123   clib_mem_free (old);
 124
 125   /* Allocator may give a bit of extra room. */
 126   new_alloc_bytes = clib_mem_size (new);
 127   v = new;
 128
 129   /* Zero new memory. */
 130   CLIB_MEM_UNPOISON (new + data_bytes, new_alloc_bytes - data_bytes);
 131   memset (v + old_alloc_bytes, 0, new_alloc_bytes - old_alloc_bytes);
 132   CLIB_MEM_POISON (new + data_bytes, new_alloc_bytes - data_bytes);
 133
 134   _vec_numa ((v + header_bytes)) = numa_id;
 135   if (PREDICT_FALSE (numa_id != VEC_NUMA_UNSPECIFIED))
 136     clib_mem_set_per_cpu_heap (oldheap);
 137
 138   return v + header_bytes;
 139 }
 140
 141 __clib_export uword
 142 clib_mem_is_vec_h (void *v, uword header_bytes)
 143 {
 144   return clib_mem_is_heap_object (vec_header (v, header_bytes));
 145 }
 146
 147 __clib_export u32
 148 vec_len_not_inline (void *v)
 149 {
 150   return vec_len (v);
 151 }
 152
 153 __clib_export void
 154 vec_free_not_inline (void *v)
 155 {
 156   vec_free (v);
 157 }
 158
 159 /** \cond */
 160
 161 #ifdef TEST
 162
 163 #include <stdio.h>
 164
 165 void
 166 main (int argc, char *argv[])
 167 {
 168   word n = atoi (argv[1]);
 169   word i, *x = 0;
 170
 171   typedef struct
 172   {
 173     word x, y, z;
 174   } FOO;
 175
 176   FOO *foos = vec_init (FOO, 10), *f;
 177
 178   vec_validate (foos, 100);
 179   foos[100].x = 99;
 180
 181   _vec_len (foos) = 0;
 182   for (i = 0; i < n; i++)
 183     {
 184       vec_add1 (x, i);
 185       vec_add2 (foos, f, 1);
 186       f->x = 2 * i;
 187       f->y = 3 * i;
 188       f->z = 4 * i;
 189     }
 190
 191   {
 192     word n = 2;
 193     word m = 42;
 194     vec_delete (foos, n, m);
 195   }
 196
 197   {
 198     word n = 2;
 199     word m = 42;
 200     vec_insert (foos, n, m);
 201   }
 202
 203   vec_free (x);
 204   vec_free (foos);
 205   exit (0);
 206 }
 207 #endif
 208 /** \endcond */
 209
 210 /*
 211  * fd.io coding-style-patch-verification: ON
 212  *
 213  * Local Variables:
 214  * eval: (c-set-style "gnu")
 215  * End:
 216  */