chunk.c

   1 /*
   2 Copyright (c) 2003-2006 by Juliusz Chroboczek
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to deal
   6 in the Software without restriction, including without limitation the rights
   7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8 copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20 THE SOFTWARE.
  21 */
  22
  23 #include "polipo.h"
  24
  25 #define MB (1024 * 1024)
  26 int chunkLowMark = 0,
  27     chunkCriticalMark = 0,
  28     chunkHighMark = 8 * MB;
  29
  30 void
  31 preinitChunks()
  32 {
  33     CONFIG_VARIABLE(chunkLowMark, CONFIG_INT,
  34                     "Low mark for chunk memory (0 = auto).");
  35     CONFIG_VARIABLE(chunkCriticalMark, CONFIG_INT,
  36                     "Critical mark for chunk memory (0 = auto).");
  37     CONFIG_VARIABLE(chunkHighMark, CONFIG_INT,
  38                     "High mark for chunk memory.");
  39 }
  40
  41 static void
  42 initChunksCommon()
  43 {
  44 #define ROUND_CHUNKS(a) a = (((a) + CHUNK_SIZE - 1) / CHUNK_SIZE) * CHUNK_SIZE;
  45     int q;
  46
  47     if(CHUNK_SIZE != 1 << log2_ceil(CHUNK_SIZE)) {
  48         do_log(L_ERROR, "CHUNK SIZE %d is not a power of two.\n", CHUNK_SIZE);
  49         exit(1);
  50     }
  51
  52     ROUND_CHUNKS(chunkHighMark);
  53     ROUND_CHUNKS(chunkCriticalMark);
  54     ROUND_CHUNKS(chunkLowMark);
  55
  56     if(chunkHighMark < 8 * CHUNK_SIZE) {
  57         chunkHighMark = 8 * CHUNK_SIZE;
  58         do_log(L_WARN, "Impossibly low chunkHighMark -- setting to %d.\n",
  59                chunkHighMark);
  60     }
  61
  62     q = 0;
  63     if(chunkLowMark <= 0) q = 1;
  64     if(chunkLowMark < 4 * CHUNK_SIZE ||
  65        chunkLowMark > chunkHighMark - 4 * CHUNK_SIZE) {
  66         chunkLowMark = MIN(chunkHighMark - 4 * CHUNK_SIZE,
  67                            chunkHighMark * 3 / 4);
  68         ROUND_CHUNKS(chunkLowMark);
  69         if(!q) do_log(L_WARN, "Inconsistent chunkLowMark -- setting to %d.\n",
  70                       chunkLowMark);
  71     }
  72
  73     q = 0;
  74     if(chunkCriticalMark <= 0) q = 1;
  75     if(chunkCriticalMark >= chunkHighMark - 2 * CHUNK_SIZE ||
  76        chunkCriticalMark <= chunkLowMark + 2 * CHUNK_SIZE) {
  77         chunkCriticalMark =
  78             MIN(chunkHighMark - 2 * CHUNK_SIZE,
  79                 chunkLowMark + (chunkHighMark - chunkLowMark) * 15 / 16);
  80         ROUND_CHUNKS(chunkCriticalMark);
  81         if(!q) do_log(L_WARN, "Inconsistent chunkCriticalMark -- "
  82                       "setting to %d.\n", chunkCriticalMark);
  83     }
  84 #undef ROUND_CHUNKS
  85 }
  86
  87
  88 int used_chunks = 0;
  89
  90 static void
  91 maybe_free_chunks(int arenas, int force)
  92 {
  93     if(force || used_chunks >= CHUNKS(chunkHighMark)) {
  94         discardObjects(force, force);
  95     }
  96
  97     if(arenas)
  98         free_chunk_arenas();
  99
 100     if(used_chunks >= CHUNKS(chunkLowMark) && !objectExpiryScheduled) {
 101         TimeEventHandlerPtr event;
 102         event = scheduleTimeEvent(1, discardObjectsHandler, 0, NULL);
 103         if(event)
 104             objectExpiryScheduled = 1;
 105     }
 106 }
 107
 108
 109
 110 #ifdef MALLOC_CHUNKS
 111
 112 void
 113 initChunks(void)
 114 {
 115     do_log(L_WARN, "Warning: using malloc(3) for chunk allocation.\n");
 116     used_chunks = 0;
 117     initChunksCommon();
 118 }
 119
 120 void
 121 free_chunk_arenas()
 122 {
 123     return;
 124 }
 125
 126 void *
 127 get_chunk()
 128 {
 129     void *chunk;
 130
 131     if(used_chunks > CHUNKS(chunkHighMark))
 132         maybe_free_chunks(0, 0);
 133     if(used_chunks > CHUNKS(chunkHighMark))
 134         return NULL;
 135     chunk = malloc(CHUNK_SIZE);
 136     if(!chunk) {
 137         maybe_free_chunks(1, 1);
 138         chunk = malloc(CHUNK_SIZE);
 139         if(!chunk)
 140             return NULL;
 141     }
 142     used_chunks++;
 143     return chunk;
 144 }
 145
 146 void *
 147 maybe_get_chunk()
 148 {
 149     void *chunk;
 150     if(used_chunks > CHUNKS(chunkHighMark))
 151         return NULL;
 152     chunk = malloc(CHUNK_SIZE);
 153     if(chunk)
 154         used_chunks++;
 155     return chunk;
 156 }
 157
 158 void
 159 dispose_chunk(void *chunk)
 160 {
 161     assert(chunk != NULL);
 162     free(chunk);
 163     used_chunks--;
 164 }
 165
 166 void
 167 free_chunks()
 168 {
 169     return;
 170 }
 171
 172 int
 173 totalChunkArenaSize()
 174 {
 175     return used_chunks * CHUNK_SIZE;
 176 }
 177 #else
 178
 179 #ifdef MINGW
 180 #define MAP_FAILED NULL
 181 #define getpagesize() (64 * 1024)
 182 static void *
 183 alloc_arena(size_t size)
 184 {
 185     return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
 186 }
 187 static int
 188 free_arena(void *addr, size_t size)
 189 {
 190     int rc;
 191     rc = VirtualFree(addr, size, MEM_RELEASE);
 192     if(!rc)
 193         rc = -1;
 194     return rc;
 195 }
 196 #else
 197 #ifndef MAP_FAILED
 198 #define MAP_FAILED ((void*)((long int)-1))
 199 #endif
 200 static void *
 201 alloc_arena(size_t size)
 202 {
 203     return mmap(NULL, size, PROT_READ | PROT_WRITE,
 204                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 205 }
 206 static int
 207 free_arena(void *addr, size_t size)
 208 {
 209     return munmap(addr, size);
 210 }
 211 #endif
 212
 213 /* Memory is organised into a number of chunks of ARENA_CHUNKS chunks
 214    each.  Every arena is pointed at by a struct _ChunkArena. */
 215 /* If currentArena is not NULL, it points at the last arena used,
 216    which gives very fast dispose/get sequences. */
 217
 218 #define DEFINE_FFS(type, ffs_name) \
 219 int \
 220 ffs_name(type i) \
 221 { \
 222     int n; \
 223     if(i == 0) return 0; \
 224     n = 1; \
 225     while((i & 1) == 0) { \
 226         i >>= 1; \
 227         n++; \
 228     } \
 229     return n; \
 230 }
 231
 232 #ifndef LONG_LONG_ARENA_BITMAPS
 233 #ifndef LONG_ARENA_BITMAPS
 234 #ifndef HAVE_FFS
 235 DEFINE_FFS(int, ffs)
 236 #endif
 237 typedef unsigned int ChunkBitmap;
 238 #define BITMAP_FFS(bitmap) (ffs(bitmap))
 239
 240 #else
 241
 242 #ifndef HAVE_FFSL
 243 DEFINE_FFS(long, ffsl)
 244 #endif
 245 typedef unsigned long ChunkBitmap;
 246 #define BITMAP_FFS(bitmap) (ffsl(bitmap))
 247 #endif
 248
 249 #else
 250
 251 #ifndef HAVE_FFSLL
 252 DEFINE_FFS(long long, ffsll)
 253 #endif
 254 typedef unsigned long long ChunkBitmap;
 255 #define BITMAP_FFS(bitmap) (ffsll(bitmap))
 256 #endif
 257
 258 #define ARENA_CHUNKS ((int)sizeof(ChunkBitmap) * 8)
 259 #define EMPTY_BITMAP (~(ChunkBitmap)0)
 260 #define BITMAP_BIT(i) (((ChunkBitmap)1) << (i))
 261
 262 static int pagesize;
 263 typedef struct _ChunkArena {
 264     ChunkBitmap bitmap;
 265     char *chunks;
 266 } ChunkArenaRec, *ChunkArenaPtr;
 267
 268 static ChunkArenaPtr chunkArenas, currentArena;
 269 static int numArenas;
 270 #define CHUNK_IN_ARENA(chunk, arena) \
 271   ((arena)->chunks && \
 272    (char*)(chunk) >= (arena)->chunks && \
 273    (char*)(chunk) < (arena)->chunks + (ARENA_CHUNKS * CHUNK_SIZE))
 274
 275 #define CHUNK_ARENA_INDEX(chunk, arena) \
 276   (((char*)(chunk) - (arena)->chunks) / CHUNK_SIZE)
 277
 278 void
 279 initChunks(void)
 280 {
 281     int i;
 282     used_chunks = 0;
 283     initChunksCommon();
 284     pagesize = getpagesize();
 285     if((CHUNK_SIZE * ARENA_CHUNKS) % pagesize != 0) {
 286         do_log(L_ERROR,
 287                "The arena size %d (%d x %d) "
 288                "is not a multiple of the page size %d.\n",
 289                 ARENA_CHUNKS * CHUNK_SIZE, ARENA_CHUNKS, CHUNK_SIZE, pagesize);
 290         abort();
 291     }
 292     numArenas =
 293         (CHUNKS(chunkHighMark) + (ARENA_CHUNKS - 1)) / ARENA_CHUNKS;
 294     chunkArenas = malloc(numArenas * sizeof(ChunkArenaRec));
 295     if(chunkArenas == NULL) {
 296         do_log(L_ERROR, "Couldn't allocate chunk arenas.\n");
 297         polipoExit();
 298     }
 299     for(i = 0; i < numArenas; i++) {
 300         chunkArenas[i].bitmap = EMPTY_BITMAP;
 301         chunkArenas[i].chunks = NULL;
 302     }
 303     currentArena = NULL;
 304 }
 305
 306 static ChunkArenaPtr
 307 findArena()
 308 {
 309     ChunkArenaPtr arena = NULL;
 310     int i;
 311
 312     for(i = 0; i < numArenas; i++) {
 313         arena = &(chunkArenas[i]);
 314         if(arena->bitmap != 0)
 315             break;
 316         else
 317             arena = NULL;
 318     }
 319
 320     assert(arena != NULL);
 321
 322     if(!arena->chunks) {
 323         void *p;
 324         p = alloc_arena(CHUNK_SIZE * ARENA_CHUNKS);
 325         if(p == MAP_FAILED) {
 326             do_log_error(L_ERROR, errno, "Couldn't allocate chunk");
 327             maybe_free_chunks(1, 1);
 328             return NULL;
 329         }
 330         arena->chunks = p;
 331     }
 332     return arena;
 333 }
 334
 335 void *
 336 get_chunk()
 337 {
 338     int i;
 339     ChunkArenaPtr arena = NULL;
 340
 341     if(currentArena && currentArena->bitmap != 0) {
 342         arena = currentArena;
 343     } else {
 344         if(used_chunks >= CHUNKS(chunkHighMark))
 345             maybe_free_chunks(0, 0);
 346
 347         if(used_chunks >= CHUNKS(chunkHighMark))
 348             return NULL;
 349
 350         arena = findArena();
 351         if(!arena)
 352             return NULL;
 353         currentArena = arena;
 354     }
 355     i = BITMAP_FFS(arena->bitmap) - 1;
 356     arena->bitmap &= ~BITMAP_BIT(i);
 357     used_chunks++;
 358     return arena->chunks + CHUNK_SIZE * i;
 359 }
 360
 361 void *
 362 maybe_get_chunk()
 363 {
 364     int i;
 365     ChunkArenaPtr arena = NULL;
 366
 367     if(currentArena && currentArena->bitmap != 0) {
 368         arena = currentArena;
 369     } else {
 370         if(used_chunks >= CHUNKS(chunkHighMark))
 371             return NULL;
 372
 373         arena = findArena();
 374         if(!arena)
 375             return NULL;
 376         currentArena = arena;
 377     }
 378     i = ffs(arena->bitmap) - 1;
 379     arena->bitmap &= ~BITMAP_BIT(i);
 380     used_chunks++;
 381     return arena->chunks + CHUNK_SIZE * i;
 382 }
 383
 384 void
 385 dispose_chunk(void *chunk)
 386 {
 387     ChunkArenaPtr arena = NULL;
 388     int i;
 389
 390     assert(chunk != NULL);
 391
 392     if(currentArena && CHUNK_IN_ARENA(chunk, currentArena)) {
 393         arena = currentArena;
 394     } else {
 395         for(i = 0; i < numArenas; i++) {
 396             arena = &(chunkArenas[i]);
 397             if(CHUNK_IN_ARENA(chunk, arena))
 398                 break;
 399         }
 400         assert(arena != NULL);
 401         currentArena = arena;
 402     }
 403
 404     i = CHUNK_ARENA_INDEX(chunk, arena);
 405     arena->bitmap |= BITMAP_BIT(i);
 406     used_chunks--;
 407 }
 408
 409 void
 410 free_chunk_arenas()
 411 {
 412     ChunkArenaPtr arena;
 413     int i, rc;
 414
 415     for(i = 0; i < numArenas; i++) {
 416         arena = &(chunkArenas[i]);
 417         if(arena->bitmap == EMPTY_BITMAP && arena->chunks) {
 418             rc = free_arena(arena->chunks, CHUNK_SIZE * ARENA_CHUNKS);
 419             if(rc < 0) {
 420                 do_log_error(L_ERROR, errno, "Couldn't unmap memory");
 421                 continue;
 422             }
 423             arena->chunks = NULL;
 424         }
 425     }
 426     if(currentArena && currentArena->chunks == NULL)
 427         currentArena = NULL;
 428 }
 429
 430 int
 431 totalChunkArenaSize()
 432 {
 433     ChunkArenaPtr arena;
 434     int i, size = 0;
 435
 436     for(i = 0; i < numArenas; i++) {
 437         arena = &(chunkArenas[i]);
 438         if(arena->chunks)
 439             size += (CHUNK_SIZE * ARENA_CHUNKS);
 440     }
 441     return size;
 442 }
 443 #endif