freelist.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167
  1. /*
  2. * Copyright (c) 2007 Damien Miller. All rights reserved.
  3. *
  4. * Redistribution and use in source and binary forms, with or without
  5. * modification, are permitted provided that the following conditions
  6. * are met:
  7. * 1. Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * 2. Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. *
  13. * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  14. * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  15. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  16. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  17. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  18. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  19. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  20. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  22. * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23. */
  24. #include "common.h"
  25. #include "freelist.h"
  26. #include "log.h"
  27. #define FREELIST_MAX_ALLOC 0x1000000
  28. #define FREELIST_ALLOC_ALIGN 16
  29. #define FREELIST_INITIAL_ALLOC 16
  30. #ifndef roundup
  31. #define roundup(x, y) ((((x) + (y) - 1)/(y))*(y))
  32. #endif /* roundup */
  33. #undef FREELIST_DEBUG
  34. #ifdef FREELIST_DEBUG
  35. # define FLOGIT(a) logit a
  36. #else
  37. # define FLOGIT(a)
  38. #endif
  39. void
  40. freelist_init(struct freelist *fl, size_t allocsz)
  41. {
  42. size_t sizeof_fl = sizeof(fl);
  43. FLOGIT((LOG_DEBUG, "%s: %s(%p, %zu)", __func__, __func__, fl, allocsz));
  44. bzero(fl, sizeof_fl);
  45. fl->allocsz = roundup(allocsz, FREELIST_ALLOC_ALIGN);
  46. fl->free_entries = NULL;
  47. }
  48. static int
  49. freelist_grow(struct freelist *fl)
  50. {
  51. size_t i, oldnalloc, need;
  52. void *p;
  53. FLOGIT((LOG_DEBUG, "%s: %s(%p)", __func__, __func__, fl));
  54. FLOGIT((LOG_DEBUG, "%s: nalloc = %zu", __func__, fl->nalloc));
  55. /* Sanity check */
  56. if (fl->nalloc > FREELIST_MAX_ALLOC)
  57. return -1;
  58. oldnalloc = fl->nalloc;
  59. if (fl->nalloc == 0)
  60. fl->nalloc = FREELIST_INITIAL_ALLOC;
  61. else
  62. fl->nalloc <<= 1;
  63. if (fl->nalloc > FREELIST_MAX_ALLOC)
  64. fl->nalloc = FREELIST_MAX_ALLOC;
  65. FLOGIT((LOG_DEBUG, "%s: nalloc now %zu", __func__, fl->nalloc));
  66. /* Check for integer overflow */
  67. if (SIZE_MAX / fl->nalloc < fl->allocsz ||
  68. SIZE_MAX / fl->nalloc < sizeof(*fl->free_entries)) {
  69. FLOGIT((LOG_DEBUG, "%s: integer overflow", __func__));
  70. resize_fail:
  71. fl->nalloc = oldnalloc;
  72. return -1;
  73. }
  74. /* Allocate freelist - max size of nalloc */
  75. need = fl->nalloc * sizeof(*fl->free_entries);
  76. if ((p = realloc(fl->free_entries, need)) == NULL) {
  77. FLOGIT((LOG_DEBUG, "%s: realloc(%zu) failed", __func__, need));
  78. goto resize_fail;
  79. }
  80. /* Allocate the entries */
  81. fl->free_entries = p;
  82. need = (fl->nalloc - oldnalloc) * fl->allocsz;
  83. if ((p = malloc(need)) == NULL) {
  84. FLOGIT((LOG_DEBUG, "%s: malloc(%zu) failed", __func__, need));
  85. goto resize_fail;
  86. }
  87. /*
  88. * XXX store these malloc ranges in a tree or list, so we can
  89. * validate them in _get/_put. Check that r_low <= addr < r_high, and
  90. * (addr - r_low) % fl->allocsz == 0
  91. */
  92. fl->navail = fl->nalloc - oldnalloc;
  93. for (i = 0; i < fl->navail; i++)
  94. fl->free_entries[i] = (u_char *)p + (i * fl->allocsz);
  95. for (i = fl->navail; i < fl->nalloc; i++)
  96. fl->free_entries[i] = NULL;
  97. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  98. return 0;
  99. }
  100. void *
  101. freelist_get(struct freelist *fl)
  102. {
  103. void *r;
  104. FLOGIT((LOG_DEBUG, "%s: %s(%p)", __func__, __func__, fl));
  105. FLOGIT((LOG_DEBUG, "%s: navail = %zu", __func__, fl->navail));
  106. if (fl->navail == 0) {
  107. if (freelist_grow(fl) == -1)
  108. return NULL;
  109. }
  110. /* Sanity check */
  111. if (fl->navail == 0 || fl->navail > FREELIST_MAX_ALLOC ||
  112. fl->free_entries[fl->navail - 1] == NULL) {
  113. logit(LOG_ERR, "%s: invalid navail", __func__);
  114. raise(SIGSEGV);
  115. }
  116. fl->navail--;
  117. r = fl->free_entries[fl->navail];
  118. fl->free_entries[fl->navail] = NULL;
  119. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  120. return r;
  121. }
  122. void
  123. freelist_put(struct freelist *fl, void *p)
  124. {
  125. FLOGIT((LOG_DEBUG, "%s: %s(%p, %zu)", __func__, __func__, fl, p));
  126. FLOGIT((LOG_DEBUG, "%s: navail = %zu", __func__, fl->navail));
  127. FLOGIT((LOG_DEBUG, "%s: nalloc = %zu", __func__, fl->navail));
  128. /* Sanity check */
  129. if (fl->navail >= fl->nalloc) {
  130. logit(LOG_ERR, "%s: freelist navail >= nalloc", __func__);
  131. raise(SIGSEGV);
  132. }
  133. if (fl->free_entries[fl->navail] != NULL) {
  134. logit(LOG_ERR, "%s: free_entries[%lu] != NULL",
  135. __func__, (unsigned long)fl->navail);
  136. raise(SIGSEGV);
  137. }
  138. fl->free_entries[fl->navail] = p;
  139. fl->navail++;
  140. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  141. }