freelist.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  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. FLOGIT((LOG_DEBUG, "%s: %s(%p, %zu)", __func__, __func__, fl, allocsz));
  43. bzero(fl, sizeof(fl));
  44. fl->allocsz = roundup(allocsz, FREELIST_ALLOC_ALIGN);
  45. fl->free_entries = NULL;
  46. }
  47. static int
  48. freelist_grow(struct freelist *fl)
  49. {
  50. size_t i, oldnalloc, need;
  51. void *p;
  52. FLOGIT((LOG_DEBUG, "%s: %s(%p)", __func__, __func__, fl));
  53. FLOGIT((LOG_DEBUG, "%s: nalloc = %zu", __func__, fl->nalloc));
  54. /* Sanity check */
  55. if (fl->nalloc > FREELIST_MAX_ALLOC)
  56. return -1;
  57. oldnalloc = fl->nalloc;
  58. if (fl->nalloc == 0)
  59. fl->nalloc = FREELIST_INITIAL_ALLOC;
  60. else
  61. fl->nalloc <<= 1;
  62. if (fl->nalloc > FREELIST_MAX_ALLOC)
  63. fl->nalloc = FREELIST_MAX_ALLOC;
  64. FLOGIT((LOG_DEBUG, "%s: nalloc now %zu", __func__, fl->nalloc));
  65. /* Check for integer overflow */
  66. if (SIZE_MAX / fl->nalloc < fl->allocsz ||
  67. SIZE_MAX / fl->nalloc < sizeof(*fl->free_entries)) {
  68. FLOGIT((LOG_DEBUG, "%s: integer overflow", __func__));
  69. resize_fail:
  70. fl->nalloc = oldnalloc;
  71. return -1;
  72. }
  73. /* Allocate freelist - max size of nalloc */
  74. need = fl->nalloc * sizeof(*fl->free_entries);
  75. if ((p = realloc(fl->free_entries, need)) == NULL) {
  76. FLOGIT((LOG_DEBUG, "%s: realloc(%zu) failed", __func__, need));
  77. goto resize_fail;
  78. }
  79. /* Allocate the entries */
  80. fl->free_entries = p;
  81. need = (fl->nalloc - oldnalloc) * fl->allocsz;
  82. if ((p = malloc(need)) == NULL) {
  83. FLOGIT((LOG_DEBUG, "%s: malloc(%zu) failed", __func__, need));
  84. goto resize_fail;
  85. }
  86. /*
  87. * XXX store these malloc ranges in a tree or list, so we can
  88. * validate them in _get/_put. Check that r_low <= addr < r_high, and
  89. * (addr - r_low) % fl->allocsz == 0
  90. */
  91. fl->navail = fl->nalloc - oldnalloc;
  92. for (i = 0; i < fl->navail; i++)
  93. fl->free_entries[i] = (u_char *)p + (i * fl->allocsz);
  94. for (i = fl->navail; i < fl->nalloc; i++)
  95. fl->free_entries[i] = NULL;
  96. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  97. return 0;
  98. }
  99. void *
  100. freelist_get(struct freelist *fl)
  101. {
  102. void *r;
  103. FLOGIT((LOG_DEBUG, "%s: %s(%p)", __func__, __func__, fl));
  104. FLOGIT((LOG_DEBUG, "%s: navail = %zu", __func__, fl->navail));
  105. if (fl->navail == 0) {
  106. if (freelist_grow(fl) == -1)
  107. return NULL;
  108. }
  109. /* Sanity check */
  110. if (fl->navail == 0 || fl->navail > FREELIST_MAX_ALLOC ||
  111. fl->free_entries[fl->navail - 1] == NULL) {
  112. logit(LOG_ERR, "%s: invalid navail", __func__);
  113. raise(SIGSEGV);
  114. }
  115. fl->navail--;
  116. r = fl->free_entries[fl->navail];
  117. fl->free_entries[fl->navail] = NULL;
  118. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  119. return r;
  120. }
  121. void
  122. freelist_put(struct freelist *fl, void *p)
  123. {
  124. FLOGIT((LOG_DEBUG, "%s: %s(%p, %zu)", __func__, __func__, fl, p));
  125. FLOGIT((LOG_DEBUG, "%s: navail = %zu", __func__, fl->navail));
  126. FLOGIT((LOG_DEBUG, "%s: nalloc = %zu", __func__, fl->navail));
  127. /* Sanity check */
  128. if (fl->navail >= fl->nalloc) {
  129. logit(LOG_ERR, "%s: freelist navail >= nalloc", __func__);
  130. raise(SIGSEGV);
  131. }
  132. if (fl->free_entries[fl->navail] != NULL) {
  133. logit(LOG_ERR, "%s: free_entries[%lu] != NULL",
  134. __func__, (unsigned long)fl->navail);
  135. raise(SIGSEGV);
  136. }
  137. fl->free_entries[fl->navail] = p;
  138. fl->navail++;
  139. FLOGIT((LOG_DEBUG, "%s: done, navail = %zu", __func__, fl->navail));
  140. }