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 = 0;
  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 = (((unsigned long)(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         int mem = physicalMemory();
  58         if(mem > 0)
  59             chunkHighMark = mem / 4;
  60         else
  61             chunkHighMark = 24 * MB;
  62         chunkHighMark = MIN(chunkHighMark, 24 * MB);
  63         chunkHighMark = MAX(chunkHighMark, 8 * CHUNK_SIZE);
  64     }
  65
  66     if(chunkHighMark < MB / 2)
  67         fprintf(stderr,
  68                 "Warning: little chunk memory (%d bytes)\n", chunkHighMark);
  69
  70     q = 0;
  71     if(chunkLowMark <= 0) q = 1;
  72     if(chunkLowMark < 4 * CHUNK_SIZE ||
  73        chunkLowMark > chunkHighMark - 4 * CHUNK_SIZE) {
  74         chunkLowMark = MIN(chunkHighMark - 4 * CHUNK_SIZE,
  75                            chunkHighMark * 3 / 4);
  76         ROUND_CHUNKS(chunkLowMark);
  77         if(!q) do_log(L_WARN, "Inconsistent chunkLowMark -- setting to %d.\n",
  78                       chunkLowMark);
  79     }
  80
  81     q = 0;
  82     if(chunkCriticalMark <= 0) q = 1;
  83     if(chunkCriticalMark >= chunkHighMark - 2 * CHUNK_SIZE ||
  84        chunkCriticalMark <= chunkLowMark + 2 * CHUNK_SIZE) {
  85         chunkCriticalMark =
  86             MIN(chunkHighMark - 2 * CHUNK_SIZE,
  87                 chunkLowMark + (chunkHighMark - chunkLowMark) * 15 / 16);
  88         ROUND_CHUNKS(chunkCriticalMark);
  89         if(!q) do_log(L_WARN, "Inconsistent chunkCriticalMark -- "
  90                       "setting to %d.\n", chunkCriticalMark);
  91     }
  92 #undef ROUND_CHUNKS
  93 }
  94
  95
  96 int used_chunks = 0;
  97
  98 static void
  99 maybe_free_chunks(int arenas, int force)
 100 {
 101     if(force || used_chunks >= CHUNKS(chunkHighMark)) {
 102         discardObjects(force, force);
 103     }
 104
 105     if(arenas)
 106         free_chunk_arenas();
 107
 108     if(used_chunks >= CHUNKS(chunkLowMark) && !objectExpiryScheduled) {
 109         TimeEventHandlerPtr event;
 110         event = scheduleTimeEvent(1, discardObjectsHandler, 0, NULL);
 111         if(event)
 112             objectExpiryScheduled = 1;
 113     }
 114 }
 115
 116
 117
 118 #ifdef MALLOC_CHUNKS
 119
 120 void
 121 initChunks(void)
 122 {
 123     do_log(L_WARN, "Warning: using malloc(3) for chunk allocation.\n");
 124     used_chunks = 0;
 125     initChunksCommon();
 126 }
 127
 128 void
 129 free_chunk_arenas()
 130 {
 131     return;
 132 }
 133
 134 void *
 135 get_chunk()
 136 {
 137     void *chunk;
 138
 139     if(used_chunks > CHUNKS(chunkHighMark))
 140         maybe_free_chunks(0, 0);
 141     if(used_chunks > CHUNKS(chunkHighMark))
 142         return NULL;
 143     chunk = malloc(CHUNK_SIZE);
 144     if(!chunk) {
 145         maybe_free_chunks(1, 1);
 146         chunk = malloc(CHUNK_SIZE);
 147         if(!chunk)
 148             return NULL;
 149     }
 150     used_chunks++;
 151     return chunk;
 152 }
 153
 154 void *
 155 maybe_get_chunk()
 156 {
 157     void *chunk;
 158     if(used_chunks > CHUNKS(chunkHighMark))
 159         return NULL;
 160     chunk = malloc(CHUNK_SIZE);
 161     if(chunk)
 162         used_chunks++;
 163     return chunk;
 164 }
 165
 166 void
 167 dispose_chunk(void *chunk)
 168 {
 169     assert(chunk != NULL);
 170     free(chunk);
 171     used_chunks--;
 172 }
 173
 174 void
 175 free_chunks()
 176 {
 177     return;
 178 }
 179
 180 int
 181 totalChunkArenaSize()
 182 {
 183     return used_chunks * CHUNK_SIZE;
 184 }
 185 #else
 186
 187 #ifdef WIN32 /*MINGW*/
 188 #define MAP_FAILED NULL
 189 #define getpagesize() (64 * 1024)
 190 static void *
 191 alloc_arena(size_t size)
 192 {
 193     return VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
 194 }
 195 static int
 196 free_arena(void *addr, size_t size)
 197 {
 198     int rc;
 199     rc = VirtualFree(addr, size, MEM_RELEASE);
 200     if(!rc)
 201         rc = -1;
 202     return rc;
 203 }
 204 #else
 205 #ifndef MAP_FAILED
 206 #define MAP_FAILED ((void*)((long int)-1))
 207 #endif
 208 static void *
 209 alloc_arena(size_t size)
 210 {
 211     return mmap(NULL, size, PROT_READ | PROT_WRITE,
 212                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 213 }
 214 static int
 215 free_arena(void *addr, size_t size)
 216 {
 217     return munmap(addr, size);
 218 }
 219 #endif
 220
 221 /* Memory is organised into a number of chunks of ARENA_CHUNKS chunks
 222    each.  Every arena is pointed at by a struct _ChunkArena. */
 223 /* If currentArena is not NULL, it points at the last arena used,
 224    which gives very fast dispose/get sequences. */
 225
 226 #define DEFINE_FFS(type, ffs_name) \
 227 int                           \
 228 ffs_name(type i)              \
 229 {                             \
 230     int n;                    \
 231     if(i == 0) return 0;      \
 232     n = 1;                    \
 233     while((i & 1) == 0) {     \
 234         i >>= 1;              \
 235         n++;                  \
 236     }                         \
 237     return n;                 \
 238 }
 239
 240 #if defined(DEFAULT_ARENA_BITMAPS) + defined(LONG_ARENA_BITMAPS) + defined(LONG_LONG_ARENA_BITMAPS) > 1
 241 #error "Multiple sizes of arenas defined"
 242 #endif
 243
 244 #if defined(DEFAULT_ARENA_BITMAPS) + defined(LONG_ARENA_BITMAPS) + defined(LONG_LONG_ARENA_BITMAPS) == 0
 245 #ifdef HAVE_FFSL
 246 /* This gives us 32-bit arena bitmaps on LP32, and 64-bit ones on LP64 */
 247 #define LONG_ARENA_BITMAPS
 248 #else
 249 #define DEFAULT_ARENA_BITMAPS
 250 #endif
 251 #endif
 252
 253 #if defined(DEFAULT_ARENA_BITMAPS)
 254
 255 #ifndef HAVE_FFS
 256 DEFINE_FFS(int, ffs)
 257 #endif
 258 typedef unsigned int ChunkBitmap;
 259 #define BITMAP_FFS(bitmap) (ffs(bitmap))
 260
 261 #elif defined(LONG_ARENA_BITMAPS)
 262
 263 #ifndef HAVE_FFSL
 264 DEFINE_FFS(long, ffsl)
 265 #endif
 266 typedef unsigned long ChunkBitmap;
 267 #define BITMAP_FFS(bitmap) (ffsl(bitmap))
 268
 269 #elif defined(LONG_LONG_ARENA_BITMAPS)
 270
 271 #ifndef HAVE_FFSLL
 272 DEFINE_FFS(long long, ffsll)
 273 #endif
 274 typedef unsigned long long ChunkBitmap;
 275 #define BITMAP_FFS(bitmap) (ffsll(bitmap))
 276
 277 #else
 278
 279 #error "You lose"
 280
 281 #endif
 282
 283 #define ARENA_CHUNKS ((unsigned)sizeof(ChunkBitmap) * 8)
 284 #define EMPTY_BITMAP (~(ChunkBitmap)0)
 285 #define BITMAP_BIT(i) (((ChunkBitmap)1) << (i))
 286
 287 static int pagesize;
 288 typedef struct _ChunkArena {
 289     ChunkBitmap bitmap;
 290     char *chunks;
 291 } ChunkArenaRec, *ChunkArenaPtr;
 292
 293 static ChunkArenaPtr chunkArenas, currentArena;
 294 static int numArenas;
 295 #define CHUNK_IN_ARENA(chunk, arena)                                    \
 296     ((arena)->chunks &&                                                 \
 297      (char*)(chunk) >= (arena)->chunks &&                               \
 298      (char*)(chunk) < (arena)->chunks + (ARENA_CHUNKS * CHUNK_SIZE))
 299
 300 #define CHUNK_ARENA_INDEX(chunk, arena)                                 \
 301     ((unsigned)((unsigned long)(((char*)(chunk) - (arena)->chunks)) /   \
 302                 CHUNK_SIZE))
 303
 304 void
 305 initChunks(void)
 306 {
 307     int i;
 308     used_chunks = 0;
 309     initChunksCommon();
 310     pagesize = getpagesize();
 311     if((CHUNK_SIZE * ARENA_CHUNKS) % pagesize != 0) {
 312         do_log(L_ERROR,
 313                "The arena size %d (%d x %d) "
 314                "is not a multiple of the page size %d.\n",
 315                 ARENA_CHUNKS * CHUNK_SIZE, ARENA_CHUNKS, CHUNK_SIZE, pagesize);
 316         abort();
 317     }
 318     numArenas =
 319         (CHUNKS(chunkHighMark) + (ARENA_CHUNKS - 1)) / ARENA_CHUNKS;
 320     chunkArenas = malloc(numArenas * sizeof(ChunkArenaRec));
 321     if(chunkArenas == NULL) {
 322         do_log(L_ERROR, "Couldn't allocate chunk arenas.\n");
 323         exit (1);
 324     }
 325     for(i = 0; i < numArenas; i++) {
 326         chunkArenas[i].bitmap = EMPTY_BITMAP;
 327         chunkArenas[i].chunks = NULL;
 328     }
 329     currentArena = NULL;
 330 }
 331
 332 static ChunkArenaPtr
 333 findArena()
 334 {
 335     ChunkArenaPtr arena = NULL;
 336     int i;
 337
 338     for(i = 0; i < numArenas; i++) {
 339         arena = &(chunkArenas[i]);
 340         if(arena->bitmap != 0)
 341             break;
 342         else
 343             arena = NULL;
 344     }
 345
 346     assert(arena != NULL);
 347
 348     if(!arena->chunks) {
 349         void *p;
 350         p = alloc_arena(CHUNK_SIZE * ARENA_CHUNKS);
 351         if(p == MAP_FAILED) {
 352             do_log_error(L_ERROR, errno, "Couldn't allocate chunk");
 353             maybe_free_chunks(1, 1);
 354             return NULL;
 355         }
 356         arena->chunks = p;
 357     }
 358     return arena;
 359 }
 360
 361 void *
 362 get_chunk()
 363 {
 364     unsigned i;
 365     ChunkArenaPtr arena = NULL;
 366
 367     if(currentArena && currentArena->bitmap != 0) {
 368         arena = currentArena;
 369     } else {
 370         if(used_chunks >= CHUNKS(chunkHighMark))
 371             maybe_free_chunks(0, 0);
 372
 373         if(used_chunks >= CHUNKS(chunkHighMark))
 374             return NULL;
 375
 376         arena = findArena();
 377         if(!arena)
 378             return NULL;
 379         currentArena = arena;
 380     }
 381     i = BITMAP_FFS(arena->bitmap) - 1;
 382     arena->bitmap &= ~BITMAP_BIT(i);
 383     used_chunks++;
 384     return arena->chunks + CHUNK_SIZE * i;
 385 }
 386
 387 void *
 388 maybe_get_chunk()
 389 {
 390     unsigned i;
 391     ChunkArenaPtr arena = NULL;
 392
 393     if(currentArena && currentArena->bitmap != 0) {
 394         arena = currentArena;
 395     } else {
 396         if(used_chunks >= CHUNKS(chunkHighMark))
 397             return NULL;
 398
 399         arena = findArena();
 400         if(!arena)
 401             return NULL;
 402         currentArena = arena;
 403     }
 404     i = BITMAP_FFS(arena->bitmap) - 1;
 405     arena->bitmap &= ~BITMAP_BIT(i);
 406     used_chunks++;
 407     return arena->chunks + CHUNK_SIZE * i;
 408 }
 409
 410 void
 411 dispose_chunk(void *chunk)
 412 {
 413     ChunkArenaPtr arena = NULL;
 414     unsigned i;
 415
 416     assert(chunk != NULL);
 417
 418     if(currentArena && CHUNK_IN_ARENA(chunk, currentArena)) {
 419         arena = currentArena;
 420     } else {
 421         for(i = 0; i < numArenas; i++) {
 422             arena = &(chunkArenas[i]);
 423             if(CHUNK_IN_ARENA(chunk, arena))
 424                 break;
 425         }
 426         assert(arena != NULL);
 427         currentArena = arena;
 428     }
 429
 430     i = CHUNK_ARENA_INDEX(chunk, arena);
 431     arena->bitmap |= BITMAP_BIT(i);
 432     used_chunks--;
 433 }
 434
 435 void
 436 free_chunk_arenas()
 437 {
 438     ChunkArenaPtr arena;
 439     int i, rc;
 440
 441     for(i = 0; i < numArenas; i++) {
 442         arena = &(chunkArenas[i]);
 443         if(arena->bitmap == EMPTY_BITMAP && arena->chunks) {
 444             rc = free_arena(arena->chunks, CHUNK_SIZE * ARENA_CHUNKS);
 445             if(rc < 0) {
 446                 do_log_error(L_ERROR, errno, "Couldn't unmap memory");
 447                 continue;
 448             }
 449             arena->chunks = NULL;
 450         }
 451     }
 452     if(currentArena && currentArena->chunks == NULL)
 453         currentArena = NULL;
 454 }
 455
 456 int
 457 totalChunkArenaSize()
 458 {
 459     ChunkArenaPtr arena;
 460     int i, size = 0;
 461
 462     for(i = 0; i < numArenas; i++) {
 463         arena = &(chunkArenas[i]);
 464         if(arena->chunks)
 465             size += (CHUNK_SIZE * ARENA_CHUNKS);
 466     }
 467     return size;
 468 }
 469 #endif