rubbos/app/httpd-2.0.64/srclib/apr-util/misc/apr_rmm.c

   1 /* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
   2  * applicable.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "apr_general.h"
  18 #include "apr_rmm.h"
  19 #include "apr_errno.h"
  20 #include "apr_lib.h"
  21 #include "apr_strings.h"
  22
  23 typedef struct rmm_block_t {
  24     apr_size_t size;
  25     apr_rmm_off_t prev;
  26     apr_rmm_off_t next;
  27 } rmm_block_t;
  28
  29 /* Always at our apr_rmm_off(0):
  30  */
  31 typedef struct rmm_hdr_block_t {
  32     apr_size_t abssize;
  33     apr_rmm_off_t /* rmm_block_t */ firstused;
  34     apr_rmm_off_t /* rmm_block_t */ firstfree;
  35 } rmm_hdr_block_t;
  36
  37 #define RMM_HDR_BLOCK_SIZE (APR_ALIGN_DEFAULT(sizeof(rmm_hdr_block_t)))
  38 #define RMM_BLOCK_SIZE (APR_ALIGN_DEFAULT(sizeof(rmm_block_t)))
  39
  40 struct apr_rmm_t {
  41     apr_pool_t *p;
  42     rmm_hdr_block_t *base;
  43     apr_size_t size;
  44     apr_anylock_t lock;
  45 };
  46
  47 static apr_rmm_off_t find_block_by_offset(apr_rmm_t *rmm, apr_rmm_off_t next,
  48                                           apr_rmm_off_t find, int includes)
  49 {
  50     apr_rmm_off_t prev = 0;
  51
  52     while (next) {
  53         struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + next);
  54
  55         if (find == next)
  56             return next;
  57
  58         /* Overshot? */
  59         if (find < next)
  60             return includes ? prev : 0;
  61
  62         prev = next;
  63         next = blk->next;
  64     }
  65     return includes ? prev : 0;
  66 }
  67
  68 static apr_rmm_off_t find_block_of_size(apr_rmm_t *rmm, apr_size_t size)
  69 {
  70     apr_rmm_off_t next = rmm->base->firstfree;
  71     apr_rmm_off_t best = 0;
  72     apr_rmm_off_t bestsize = 0;
  73
  74     while (next) {
  75         struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + next);
  76
  77         if (blk->size == size)
  78             return next;
  79
  80         if (blk->size >= size) {
  81             /* XXX: sub optimal algorithm
  82              * We need the most thorough best-fit logic, since we can
  83              * never grow our rmm, we are SOL when we hit the wall.
  84              */
  85             if (!bestsize || (blk->size < bestsize)) {
  86                 bestsize = blk->size;
  87                 best = next;
  88             }
  89         }
  90
  91         next = blk->next;
  92     }
  93
  94     if (bestsize > RMM_BLOCK_SIZE + size) {
  95         struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + best);
  96         struct rmm_block_t *new = (rmm_block_t*)((char*)rmm->base + best + size);
  97
  98         new->size = blk->size - size;
  99         new->next = blk->next;
 100         new->prev = best;
 101
 102         blk->size = size;
 103         blk->next = best + size;
 104
 105         if (new->next) {
 106             blk = (rmm_block_t*)((char*)rmm->base + new->next);
 107             blk->prev = best + size;
 108         }
 109     }
 110
 111     return best;
 112 }
 113
 114 static void move_block(apr_rmm_t *rmm, apr_rmm_off_t this, int free)
 115 {
 116     struct rmm_block_t *blk = (rmm_block_t*)((char*)rmm->base + this);
 117
 118     /* close the gap */
 119     if (blk->prev) {
 120         struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
 121         prev->next = blk->next;
 122     }
 123     else {
 124         if (free) {
 125             rmm->base->firstused = blk->next;
 126         }
 127         else {
 128             rmm->base->firstfree = blk->next;
 129         }
 130     }
 131     if (blk->next) {
 132         struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
 133         next->prev = blk->prev;
 134     }
 135
 136     /* now find it in the other list, pushing it to the head if required */
 137     if (free) {
 138         blk->prev = find_block_by_offset(rmm, rmm->base->firstfree, this, 1);
 139         if (!blk->prev) {
 140             blk->next = rmm->base->firstfree;
 141             rmm->base->firstfree = this;
 142         }
 143     }
 144     else {
 145         blk->prev = find_block_by_offset(rmm, rmm->base->firstused, this, 1);
 146         if (!blk->prev) {
 147             blk->next = rmm->base->firstused;
 148             rmm->base->firstused = this;
 149         }
 150     }
 151
 152     /* and open it up */
 153     if (blk->prev) {
 154         struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
 155         if (free && (blk->prev + prev->size == this)) {
 156             /* Collapse us into our predecessor */
 157             prev->size += blk->size;
 158             this = blk->prev;
 159             blk = prev;
 160         }
 161         else {
 162             blk->next = prev->next;
 163             prev->next = this;
 164         }
 165     }
 166
 167     if (blk->next) {
 168         struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
 169         if (free && (this + blk->size == blk->next)) {
 170             /* Collapse us into our successor */
 171             blk->size += next->size;
 172             blk->next = next->next;
 173             if (blk->next) {
 174                 next = (rmm_block_t*)((char*)rmm->base + blk->next);
 175                 next->prev = this;
 176             }
 177         }
 178         else {
 179             next->prev = this;
 180         }
 181     }
 182 }
 183
 184 APU_DECLARE(apr_status_t) apr_rmm_init(apr_rmm_t **rmm, apr_anylock_t *lock,
 185                                        void *base, apr_size_t size,
 186                                        apr_pool_t *p)
 187 {
 188     apr_status_t rv;
 189     rmm_block_t *blk;
 190     apr_anylock_t nulllock;
 191
 192     if (!lock) {
 193         nulllock.type = apr_anylock_none;
 194         nulllock.lock.pm = NULL;
 195         lock = &nulllock;
 196     }
 197     if ((rv = APR_ANYLOCK_LOCK(lock)) != APR_SUCCESS)
 198         return rv;
 199
 200     (*rmm) = (apr_rmm_t *)apr_pcalloc(p, sizeof(apr_rmm_t));
 201     (*rmm)->p = p;
 202     (*rmm)->base = base;
 203     (*rmm)->size = size;
 204     (*rmm)->lock = *lock;
 205
 206     (*rmm)->base->abssize = size;
 207     (*rmm)->base->firstused = 0;
 208     (*rmm)->base->firstfree = RMM_HDR_BLOCK_SIZE;
 209
 210     blk = (rmm_block_t *)((char*)base + (*rmm)->base->firstfree);
 211
 212     blk->size = size - (*rmm)->base->firstfree;
 213     blk->prev = 0;
 214     blk->next = 0;
 215
 216     return APR_ANYLOCK_UNLOCK(lock);
 217 }
 218
 219 APU_DECLARE(apr_status_t) apr_rmm_destroy(apr_rmm_t *rmm)
 220 {
 221     apr_status_t rv;
 222     rmm_block_t *blk;
 223
 224     if ((rv = APR_ANYLOCK_LOCK(&rmm->lock)) != APR_SUCCESS) {
 225         return rv;
 226     }
 227     /* Blast it all --- no going back :) */
 228     if (rmm->base->firstused) {
 229         apr_rmm_off_t this = rmm->base->firstused;
 230         do {
 231             blk = (rmm_block_t *)((char*)rmm->base + this);
 232             this = blk->next;
 233             blk->next = blk->prev = 0;
 234         } while (this);
 235         rmm->base->firstused = 0;
 236     }
 237     if (rmm->base->firstfree) {
 238         apr_rmm_off_t this = rmm->base->firstfree;
 239         do {
 240             blk = (rmm_block_t *)((char*)rmm->base + this);
 241             this = blk->next;
 242             blk->next = blk->prev = 0;
 243         } while (this);
 244         rmm->base->firstfree = 0;
 245     }
 246     rmm->base->abssize = 0;
 247     rmm->size = 0;
 248
 249     return APR_ANYLOCK_UNLOCK(&rmm->lock);
 250 }
 251
 252 APU_DECLARE(apr_status_t) apr_rmm_attach(apr_rmm_t **rmm, apr_anylock_t *lock,
 253                                          void *base, apr_pool_t *p)
 254 {
 255     apr_anylock_t nulllock;
 256
 257     if (!lock) {
 258         nulllock.type = apr_anylock_none;
 259         nulllock.lock.pm = NULL;
 260         lock = &nulllock;
 261     }
 262
 263     /* sanity would be good here */
 264     (*rmm) = (apr_rmm_t *)apr_pcalloc(p, sizeof(apr_rmm_t));
 265     (*rmm)->p = p;
 266     (*rmm)->base = base;
 267     (*rmm)->size = (*rmm)->base->abssize;
 268     (*rmm)->lock = *lock;
 269     return APR_SUCCESS;
 270 }
 271
 272 APU_DECLARE(apr_status_t) apr_rmm_detach(apr_rmm_t *rmm)
 273 {
 274     /* A noop until we introduce locked/refcounts */
 275     return APR_SUCCESS;
 276 }
 277
 278 APU_DECLARE(apr_rmm_off_t) apr_rmm_malloc(apr_rmm_t *rmm, apr_size_t reqsize)
 279 {
 280     apr_size_t size;
 281     apr_rmm_off_t this;
 282
 283     size = APR_ALIGN_DEFAULT(reqsize) + RMM_BLOCK_SIZE;
 284     if (size < reqsize) {
 285         return 0;
 286     }
 287
 288     APR_ANYLOCK_LOCK(&rmm->lock);
 289
 290     this = find_block_of_size(rmm, size);
 291
 292     if (this) {
 293         move_block(rmm, this, 0);
 294         this += RMM_BLOCK_SIZE;
 295     }
 296
 297     APR_ANYLOCK_UNLOCK(&rmm->lock);
 298     return this;
 299 }
 300
 301 APU_DECLARE(apr_rmm_off_t) apr_rmm_calloc(apr_rmm_t *rmm, apr_size_t reqsize)
 302 {
 303     apr_size_t size;
 304     apr_rmm_off_t this;
 305
 306     size = APR_ALIGN_DEFAULT(reqsize) + RMM_BLOCK_SIZE;
 307     if (size < reqsize) {
 308         return 0;
 309     }
 310
 311     APR_ANYLOCK_LOCK(&rmm->lock);
 312
 313     this = find_block_of_size(rmm, size);
 314
 315     if (this) {
 316         move_block(rmm, this, 0);
 317         this += RMM_BLOCK_SIZE;
 318         memset((char*)rmm->base + this, 0, size - RMM_BLOCK_SIZE);
 319     }
 320
 321     APR_ANYLOCK_UNLOCK(&rmm->lock);
 322     return this;
 323 }
 324
 325 APU_DECLARE(apr_rmm_off_t) apr_rmm_realloc(apr_rmm_t *rmm, void *entity,
 326                                            apr_size_t reqsize)
 327 {
 328     apr_rmm_off_t this;
 329     apr_rmm_off_t old;
 330     struct rmm_block_t *blk;
 331     apr_size_t size, oldsize;
 332
 333     if (!entity) {
 334         return apr_rmm_malloc(rmm, reqsize);
 335     }
 336
 337     size = APR_ALIGN_DEFAULT(reqsize);
 338     if (size < reqsize) {
 339         return 0;
 340     }
 341     old = apr_rmm_offset_get(rmm, entity);
 342
 343     if ((this = apr_rmm_malloc(rmm, size)) == 0) {
 344         return 0;
 345     }
 346
 347     blk = (rmm_block_t*)((char*)rmm->base + old - RMM_BLOCK_SIZE);
 348     oldsize = blk->size;
 349
 350     memcpy(apr_rmm_addr_get(rmm, this),
 351            apr_rmm_addr_get(rmm, old), oldsize < size ? oldsize : size);
 352     apr_rmm_free(rmm, old);
 353
 354     return this;
 355 }
 356
 357 APU_DECLARE(apr_status_t) apr_rmm_free(apr_rmm_t *rmm, apr_rmm_off_t this)
 358 {
 359     apr_status_t rv;
 360     struct rmm_block_t *blk;
 361
 362     /* A little sanity check is always healthy, especially here.
 363      * If we really cared, we could make this compile-time
 364      */
 365     if (this < RMM_HDR_BLOCK_SIZE + RMM_BLOCK_SIZE) {
 366         return APR_EINVAL;
 367     }
 368
 369     this -= RMM_BLOCK_SIZE;
 370
 371     blk = (rmm_block_t*)((char*)rmm->base + this);
 372
 373     if ((rv = APR_ANYLOCK_LOCK(&rmm->lock)) != APR_SUCCESS) {
 374         return rv;
 375     }
 376     if (blk->prev) {
 377         struct rmm_block_t *prev = (rmm_block_t*)((char*)rmm->base + blk->prev);
 378         if (prev->next != this) {
 379             APR_ANYLOCK_UNLOCK(&rmm->lock);
 380             return APR_EINVAL;
 381         }
 382     }
 383     else {
 384         if (rmm->base->firstused != this) {
 385             APR_ANYLOCK_UNLOCK(&rmm->lock);
 386             return APR_EINVAL;
 387         }
 388     }
 389
 390     if (blk->next) {
 391         struct rmm_block_t *next = (rmm_block_t*)((char*)rmm->base + blk->next);
 392         if (next->prev != this) {
 393             APR_ANYLOCK_UNLOCK(&rmm->lock);
 394             return APR_EINVAL;
 395         }
 396     }
 397
 398     /* Ok, it remained [apparently] sane, so unlink it
 399      */
 400     move_block(rmm, this, 1);
 401
 402     return APR_ANYLOCK_UNLOCK(&rmm->lock);
 403 }
 404
 405 APU_DECLARE(void *) apr_rmm_addr_get(apr_rmm_t *rmm, apr_rmm_off_t entity)
 406 {
 407     /* debug-sanity checking here would be good
 408      */
 409     return (void*)((char*)rmm->base + entity);
 410 }
 411
 412 APU_DECLARE(apr_rmm_off_t) apr_rmm_offset_get(apr_rmm_t *rmm, void* entity)
 413 {
 414     /* debug, or always, sanity checking here would be good
 415      * since the primitive is apr_rmm_off_t, I don't mind penalizing
 416      * inverse conversions for safety, unless someone can prove that
 417      * there is no choice in some cases.
 418      */
 419     return ((char*)entity - (char*)rmm->base);
 420 }
 421
 422 APU_DECLARE(apr_size_t) apr_rmm_overhead_get(int n)
 423 {
 424     /* overhead per block is at most APR_ALIGN_DEFAULT(1) wasted bytes
 425      * for alignment overhead, plus the size of the rmm_block_t
 426      * structure. */
 427     return RMM_HDR_BLOCK_SIZE + n * (RMM_BLOCK_SIZE + APR_ALIGN_DEFAULT(1));
 428 }