mp_alloc.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:12k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996-2002
  5.  * Sleepycat Software.  All rights reserved.
  6.  */
  7. #include "db_config.h"
  8. #ifndef lint
  9. static const char revid[] = "$Id: mp_alloc.c,v 11.31 2002/08/14 17:21:37 ubell Exp $";
  10. #endif /* not lint */
  11. #ifndef NO_SYSTEM_INCLUDES
  12. #include <sys/types.h>
  13. #include <string.h>
  14. #endif
  15. #include "db_int.h"
  16. #include "dbinc/db_shash.h"
  17. #include "dbinc/mp.h"
  18. typedef struct {
  19. DB_MPOOL_HASH *bucket;
  20. u_int32_t priority;
  21. } HS;
  22. static void __memp_bad_buffer __P((DB_MPOOL_HASH *));
  23. static void __memp_reset_lru __P((DB_ENV *, REGINFO *, MPOOL *));
  24. /*
  25.  * __memp_alloc --
  26.  * Allocate some space from a cache region.
  27.  *
  28.  * PUBLIC: int __memp_alloc __P((DB_MPOOL *,
  29.  * PUBLIC:     REGINFO *, MPOOLFILE *, size_t, roff_t *, void *));
  30.  */
  31. int
  32. __memp_alloc(dbmp, memreg, mfp, len, offsetp, retp)
  33. DB_MPOOL *dbmp;
  34. REGINFO *memreg;
  35. MPOOLFILE *mfp;
  36. size_t len;
  37. roff_t *offsetp;
  38. void *retp;
  39. {
  40. BH *bhp;
  41. DB_ENV *dbenv;
  42. DB_MPOOL_HASH *dbht, *hp, *hp_end, *hp_tmp;
  43. DB_MUTEX *mutexp;
  44. MPOOL *c_mp;
  45. MPOOLFILE *bh_mfp;
  46. size_t freed_space;
  47. u_int32_t buckets, buffers, high_priority, max_na, priority;
  48. int aggressive, ret;
  49. void *p;
  50. dbenv = dbmp->dbenv;
  51. c_mp = memreg->primary;
  52. dbht = R_ADDR(memreg, c_mp->htab);
  53. hp_end = &dbht[c_mp->htab_buckets];
  54. buckets = buffers = 0;
  55. aggressive = 0;
  56. c_mp->stat.st_alloc++;
  57. /*
  58.  * Get aggressive if we've tried to flush the number of pages as are
  59.  * in the system without finding space.
  60.  */
  61. max_na = 5 * c_mp->htab_buckets;
  62. /*
  63.  * If we're allocating a buffer, and the one we're discarding is the
  64.  * same size, we don't want to waste the time to re-integrate it into
  65.  * the shared memory free list.  If the DB_MPOOLFILE argument isn't
  66.  * NULL, we'll compare the underlying page sizes of the two buffers
  67.  * before free-ing and re-allocating buffers.
  68.  */
  69. if (mfp != NULL)
  70. len = (sizeof(BH) - sizeof(u_int8_t)) + mfp->stat.st_pagesize;
  71. R_LOCK(dbenv, memreg);
  72. /*
  73.  * On every buffer allocation we update the buffer generation number
  74.  * and check for wraparound.
  75.  */
  76. if (++c_mp->lru_count == UINT32_T_MAX)
  77. __memp_reset_lru(dbenv, memreg, c_mp);
  78. /*
  79.  * Anything newer than 1/10th of the buffer pool is ignored during
  80.  * allocation (unless allocation starts failing).
  81.  */
  82. DB_ASSERT(c_mp->lru_count > c_mp->stat.st_pages / 10);
  83. high_priority = c_mp->lru_count - c_mp->stat.st_pages / 10;
  84. /*
  85.  * First we try to allocate from free memory.  If that fails, scan the
  86.  * buffer pool to find buffers with low priorities.  We consider small
  87.  * sets of hash buckets each time to limit the amount of work needing
  88.  * to be done.  This approximates LRU, but not very well.  We either
  89.  * find a buffer of the same size to use, or we will free 3 times what
  90.  * we need in the hopes it will coalesce into a contiguous chunk of the
  91.  * right size.  In the latter case we branch back here and try again.
  92.  */
  93. alloc: if ((ret = __db_shalloc(memreg->addr, len, MUTEX_ALIGN, &p)) == 0) {
  94. if (mfp != NULL)
  95. c_mp->stat.st_pages++;
  96. R_UNLOCK(dbenv, memreg);
  97. found: if (offsetp != NULL)
  98. *offsetp = R_OFFSET(memreg, p);
  99. *(void **)retp = p;
  100. /*
  101.  * Update the search statistics.
  102.  *
  103.  * We're not holding the region locked here, these statistics
  104.  * can't be trusted.
  105.  */
  106. if (buckets != 0) {
  107. if (buckets > c_mp->stat.st_alloc_max_buckets)
  108. c_mp->stat.st_alloc_max_buckets = buckets;
  109. c_mp->stat.st_alloc_buckets += buckets;
  110. }
  111. if (buffers != 0) {
  112. if (buffers > c_mp->stat.st_alloc_max_pages)
  113. c_mp->stat.st_alloc_max_pages = buffers;
  114. c_mp->stat.st_alloc_pages += buffers;
  115. }
  116. return (0);
  117. }
  118. /*
  119.  * We re-attempt the allocation every time we've freed 3 times what
  120.  * we need.  Reset our free-space counter.
  121.  */
  122. freed_space = 0;
  123. /*
  124.  * Walk the hash buckets and find the next two with potentially useful
  125.  * buffers.  Free the buffer with the lowest priority from the buckets'
  126.  * chains.
  127.  */
  128. for (hp_tmp = NULL;;) {
  129. /* Check for wrap around. */
  130. hp = &dbht[c_mp->last_checked++];
  131. if (hp >= hp_end) {
  132. c_mp->last_checked = 0;
  133. /*
  134.  * If we've gone through all of the hash buckets, try
  135.  * an allocation.  If the cache is small, the old page
  136.  * size is small, and the new page size is large, we
  137.  * might have freed enough memory (but not 3 times the
  138.  * memory).
  139.  */
  140. goto alloc;
  141. }
  142. /*
  143.  * Skip empty buckets.
  144.  *
  145.  * We can check for empty buckets before locking as we
  146.  * only care if the pointer is zero or non-zero.
  147.  */
  148. if (SH_TAILQ_FIRST(&hp->hash_bucket, __bh) == NULL)
  149. continue;
  150. /*
  151.  * The failure mode is when there are too many buffers we can't
  152.  * write or there's not enough memory in the system.  We don't
  153.  * have a metric for deciding if allocation has no possible way
  154.  * to succeed, so we don't ever fail, we assume memory will be
  155.  * available if we wait long enough.
  156.  *
  157.  * Get aggressive if we've tried to flush 5 times the number of
  158.  * hash buckets as are in the system -- it's possible we have
  159.  * been repeatedly trying to flush the same buffers, although
  160.  * it's unlikely.  Aggressive means:
  161.  *
  162.  * a: set a flag to attempt to flush high priority buffers as
  163.  *    well as other buffers.
  164.  * b: sync the mpool to force out queue extent pages.  While we
  165.  *    might not have enough space for what we want and flushing
  166.  *    is expensive, why not?
  167.  * c: sleep for a second -- hopefully someone else will run and
  168.  *    free up some memory.  Try to allocate memory too, in case
  169.  *    the other thread returns its memory to the region.
  170.  * d: look at a buffer in every hash bucket rather than choose
  171.  *    the more preferable of two.
  172.  *
  173.  * !!!
  174.  * This test ignores pathological cases like no buffers in the
  175.  * system -- that shouldn't be possible.
  176.  */
  177. if ((++buckets % max_na) == 0) {
  178. aggressive = 1;
  179. R_UNLOCK(dbenv, memreg);
  180. (void)__memp_sync_int(
  181.     dbenv, NULL, 0, DB_SYNC_ALLOC, NULL);
  182. (void)__os_sleep(dbenv, 1, 0);
  183. R_LOCK(dbenv, memreg);
  184. goto alloc;
  185. }
  186. if (!aggressive) {
  187. /* Skip high priority buckets. */
  188. if (hp->hash_priority > high_priority)
  189. continue;
  190. /*
  191.  * Find two buckets and select the one with the lowest
  192.  * priority.  Performance testing shows that looking
  193.  * at two improves the LRUness and looking at more only
  194.  * does a little better.
  195.  */
  196. if (hp_tmp == NULL) {
  197. hp_tmp = hp;
  198. continue;
  199. }
  200. if (hp->hash_priority > hp_tmp->hash_priority)
  201. hp = hp_tmp;
  202. hp_tmp = NULL;
  203. }
  204. /* Remember the priority of the buffer we're looking for. */
  205. priority = hp->hash_priority;
  206. /* Unlock the region and lock the hash bucket. */
  207. R_UNLOCK(dbenv, memreg);
  208. mutexp = &hp->hash_mutex;
  209. MUTEX_LOCK(dbenv, mutexp);
  210. #ifdef DIAGNOSTIC
  211. __memp_check_order(hp);
  212. #endif
  213. /*
  214.  * The lowest priority page is first in the bucket, as they are
  215.  * maintained in sorted order.
  216.  *
  217.  * The buffer may have been freed or its priority changed while
  218.  * we switched from the region lock to the hash lock.  If so,
  219.  * we have to restart.  We will still take the first buffer on
  220.  * the bucket's list, though, if it has a low enough priority.
  221.  */
  222. if ((bhp = SH_TAILQ_FIRST(&hp->hash_bucket, __bh)) == NULL ||
  223.     bhp->ref != 0 || bhp->priority > priority)
  224. goto next_hb;
  225. buffers++;
  226. /* Find the associated MPOOLFILE. */
  227. bh_mfp = R_ADDR(dbmp->reginfo, bhp->mf_offset);
  228. /* If the page is dirty, pin it and write it. */
  229. ret = 0;
  230. if (F_ISSET(bhp, BH_DIRTY)) {
  231. ++bhp->ref;
  232. ret = __memp_bhwrite(dbmp, hp, bh_mfp, bhp, 0);
  233. --bhp->ref;
  234. if (ret == 0)
  235. ++c_mp->stat.st_rw_evict;
  236. } else
  237. ++c_mp->stat.st_ro_evict;
  238. /*
  239.  * If a write fails for any reason, we can't proceed.
  240.  *
  241.  * We released the hash bucket lock while doing I/O, so another
  242.  * thread may have acquired this buffer and incremented the ref
  243.  * count after we wrote it, in which case we can't have it.
  244.  *
  245.  * If there's a write error, avoid selecting this buffer again
  246.  * by making it the bucket's least-desirable buffer.
  247.  */
  248. if (ret != 0 || bhp->ref != 0) {
  249. if (ret != 0 && aggressive)
  250. __memp_bad_buffer(hp);
  251. goto next_hb;
  252. }
  253. /*
  254.  * Check to see if the buffer is the size we're looking for.
  255.  * If so, we can simply reuse it.  Else, free the buffer and
  256.  * its space and keep looking.
  257.  */
  258. if (mfp != NULL &&
  259.     mfp->stat.st_pagesize == bh_mfp->stat.st_pagesize) {
  260. __memp_bhfree(dbmp, hp, bhp, 0);
  261. p = bhp;
  262. goto found;
  263. }
  264. freed_space += __db_shsizeof(bhp);
  265. __memp_bhfree(dbmp, hp, bhp, 1);
  266. /*
  267.  * Unlock this hash bucket and re-acquire the region lock. If
  268.  * we're reaching here as a result of calling memp_bhfree, the
  269.  * hash bucket lock has already been discarded.
  270.  */
  271. if (0) {
  272. next_hb: MUTEX_UNLOCK(dbenv, mutexp);
  273. }
  274. R_LOCK(dbenv, memreg);
  275. /*
  276.  * Retry the allocation as soon as we've freed up sufficient
  277.  * space.  We're likely to have to coalesce of memory to
  278.  * satisfy the request, don't try until it's likely (possible?)
  279.  * we'll succeed.
  280.  */
  281. if (freed_space >= 3 * len)
  282. goto alloc;
  283. }
  284. /* NOTREACHED */
  285. }
  286. /*
  287.  * __memp_bad_buffer --
  288.  * Make the first buffer in a hash bucket the least desirable buffer.
  289.  */
  290. static void
  291. __memp_bad_buffer(hp)
  292. DB_MPOOL_HASH *hp;
  293. {
  294. BH *bhp, *t_bhp;
  295. u_int32_t priority;
  296. /* Remove the first buffer from the bucket. */
  297. bhp = SH_TAILQ_FIRST(&hp->hash_bucket, __bh);
  298. SH_TAILQ_REMOVE(&hp->hash_bucket, bhp, hq, __bh);
  299. /*
  300.  * Find the highest priority buffer in the bucket.  Buffers are
  301.  * sorted by priority, so it's the last one in the bucket.
  302.  *
  303.  * XXX
  304.  * Should use SH_TAILQ_LAST, but I think that macro is broken.
  305.  */
  306. priority = bhp->priority;
  307. for (t_bhp = SH_TAILQ_FIRST(&hp->hash_bucket, __bh);
  308.     t_bhp != NULL; t_bhp = SH_TAILQ_NEXT(t_bhp, hq, __bh))
  309. priority = t_bhp->priority;
  310. /*
  311.  * Set our buffer's priority to be just as bad, and append it to
  312.  * the bucket.
  313.  */
  314. bhp->priority = priority;
  315. SH_TAILQ_INSERT_TAIL(&hp->hash_bucket, bhp, hq);
  316. /* Reset the hash bucket's priority. */
  317. hp->hash_priority = SH_TAILQ_FIRST(&hp->hash_bucket, __bh)->priority;
  318. }
  319. /*
  320.  * __memp_reset_lru --
  321.  * Reset the cache LRU counter.
  322.  */
  323. static void
  324. __memp_reset_lru(dbenv, memreg, c_mp)
  325. DB_ENV *dbenv;
  326. REGINFO *memreg;
  327. MPOOL *c_mp;
  328. {
  329. BH *bhp;
  330. DB_MPOOL_HASH *hp;
  331. int bucket;
  332. /*
  333.  * Update the counter so all future allocations will start at the
  334.  * bottom.
  335.  */
  336. c_mp->lru_count -= MPOOL_BASE_DECREMENT;
  337. /* Release the region lock. */
  338. R_UNLOCK(dbenv, memreg);
  339. /* Adjust the priority of every buffer in the system. */
  340. for (hp = R_ADDR(memreg, c_mp->htab),
  341.     bucket = 0; bucket < c_mp->htab_buckets; ++hp, ++bucket) {
  342. /*
  343.  * Skip empty buckets.
  344.  *
  345.  * We can check for empty buckets before locking as we
  346.  * only care if the pointer is zero or non-zero.
  347.  */
  348. if (SH_TAILQ_FIRST(&hp->hash_bucket, __bh) == NULL)
  349. continue;
  350. MUTEX_LOCK(dbenv, &hp->hash_mutex);
  351. for (bhp = SH_TAILQ_FIRST(&hp->hash_bucket, __bh);
  352.     bhp != NULL; bhp = SH_TAILQ_NEXT(bhp, hq, __bh))
  353. if (bhp->priority != UINT32_T_MAX &&
  354.     bhp->priority > MPOOL_BASE_DECREMENT)
  355. bhp->priority -= MPOOL_BASE_DECREMENT;
  356. MUTEX_UNLOCK(dbenv, &hp->hash_mutex);
  357. }
  358. /* Reacquire the region lock. */
  359. R_LOCK(dbenv, memreg);
  360. }
  361. #ifdef DIAGNOSTIC
  362. /*
  363.  * __memp_check_order --
  364.  * Verify the priority ordering of a hash bucket chain.
  365.  *
  366.  * PUBLIC: #ifdef DIAGNOSTIC
  367.  * PUBLIC: void __memp_check_order __P((DB_MPOOL_HASH *));
  368.  * PUBLIC: #endif
  369.  */
  370. void
  371. __memp_check_order(hp)
  372. DB_MPOOL_HASH *hp;
  373. {
  374. BH *bhp;
  375. u_int32_t priority;
  376. /*
  377.  * Assumes the hash bucket is locked.
  378.  */
  379. if ((bhp = SH_TAILQ_FIRST(&hp->hash_bucket, __bh)) == NULL)
  380. return;
  381. DB_ASSERT(bhp->priority == hp->hash_priority);
  382. for (priority = bhp->priority;
  383.     (bhp = SH_TAILQ_NEXT(bhp, hq, __bh)) != NULL;
  384.     priority = bhp->priority)
  385. DB_ASSERT(priority <= bhp->priority);
  386. }
  387. #endif