{"id":780,"date":"2020-12-25T12:43:17","date_gmt":"2020-12-25T04:43:17","guid":{"rendered":"https:\/\/kylelv.com\/?p=780"},"modified":"2021-07-29T13:39:00","modified_gmt":"2021-07-29T05:39:00","slug":"csapp%ef%bc%9amalloc-lab-%e6%80%9d%e8%b7%af","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=780","title":{"rendered":"csapp\uff1amalloc lab \u601d\u8def"},"content":{"rendered":"\n<p>\u611f\u89c9\u597d\u50cf\u6ca1\u600e\u4e48\u5199\u8fc7lab\uff0c\u4e00\u65b9\u9762\u662f\u4e4b\u524dlab\u4e5f\u6ca1\u5565\u597d\u5199\u7684\uff0c\u53e6\u4e00\u65b9\u9762\u4e5f\u662f\u5927\u6982\u8001\u5e08\u4e5f\u4e0d\u8ba9\u5916\u4f20\u3002\u3002<\/p>\n\n\n\n<p>\u56e0\u6b64\u5bf9\u4e8emalloc lab\u4e5f\u53ea\u662f\u8bf4\u4e00\u4e9bhigh level\u7684\u601d\u8def\u548c\u505a\u6cd5\uff08<s>\u867d\u7136\u597d\u50cf\u8fd8\u662f\u5e76\u4e0d\u80fd\u5f97\u5230\u6ee1\u5206ww\uff08\u53ea\u670999\u96fe\uff1f<\/s>\u5999\u5999\u5999\uff0c\u679c\u7136\u8fd8\u662f\u5927\u4f6cnb\uff0c\u4ed6\u7ec8\u4e8e\u6ee1\u4e86qwq<\/p>\n\n\n\n<p>\u554a\u66fe\u7ecf\u8bf4\u8fc7\u7edd\u4e0d\u5199\u5e73\u8861\u6811\uff08\u5fc5\u7136\u53ef\u4ee5\u7528\u5176\u4ed6\u505a\u6cd5\u66ff\u4ee3\uff1f\uff09\uff0c\u7ed3\u679c\u8fd9\u91cc\u7834\u9632\u4e86\u545c\u545c\u545c\uff08\u5361\u7a7a\u95f4\uff0c\u65e0stl\u81ea\u95ed\u4e86<br>\u4e0d\u8fc7\u81f3\u5c11\u7ec3\u4e86\u4e00\u6b21treap\uff08\u81f3\u5c11\u4ee5\u540etreap\u8fd8\u4f1a\u5199\u70b9\u4e86\uff1fqwq<\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p>\u55ef\u8fd9\u4e2a\u6587\u7ae0\u6709\u4e2a\u526f\u6807\u9898\u5c31\u662f<strong>\u201c\u81ea\u5df1\u9009\u62e9\u7684\u8def\uff0c\u8dea\u7740\u4e5f\u8981\u8d70\u5b8c\u201d<\/strong><\/p>\n\n\n\n<p>&lt;del&gt;\u5c31\u662f\u542c\u4e86\u7b2c\u4e00\u4e2aa\u7684\u4eba\uff08Joker\uff09\uff08\u554a\u4e0d\u4ed6\u5c31\u662f\u5b89\u5927\u7237\uff01\uff09\u7684\u9b3c\u8bdd\uff0c\u5165\u4e86\u90aa\u6559\u5927\u5751\uff0c\u5199\u4e86\u5e73\u8861\u6811\uff0c\u7ed3\u679c\u5168\u4e16\u754c\u94fe\u886899+\uff1f\uff08\u679c\u7136\u4eba\u5982\u5176\u540d\u3002\u3002\u3002&lt;\/del&gt;<\/p>\n\n\n\n<p>\u770b\u4e86\u4e0b\u7cfb\u7edf\u5e95\u5c42libc\u5b9e\u73b0\u4e5f\u662f\u7528\u94fe\u8868\u505a\u7684\uff1f\uff08\u867d\u7136\u5e76\u6ca1\u6709\u600e\u4e48\u770b\u61c2\uff0c\u5e0c\u671b\u5982\u679c\u6709\u54ea\u4f4d\u5927\u4f6c\u770b\u61c2\u4e86\uff0c\u7ed9\u6211\u8bb2\u4e00\u8bb2qwq<\/p>\n\n\n\n<p><a href=\"https:\/\/hanfeng.ink\/post\/understand_glibc_malloc\/\" target=\"_blank\" rel=\"noopener\">https:\/\/hanfeng.ink\/post\/understand_glibc_malloc\/<\/a><\/p>\n\n\n\n<p>\u4e0d\u8fc7\u5165\u4e86\u5e73\u8861\u6811\u7684\u5751\uff0c\u722c\u4e5f\u662f\u8981\u722c\u5b8c\u7684\uff01<\/p>\n\n\n\n<p>\uff08\u4e2d\u95f4\u5199\u4e86\u65e0\u6570\u7248\u672c\uff08\u7adf\u7136\u90fd\u6ca1\u6709\u6837\u4f8b\u5206\u9ad8\u545c\u545c<\/p>\n\n\n\n<p>\u5199\u4e4b\u524d\u8ba4\u771f\u770b\u4e00\u904d\u4e66\u611f\u89c9\u662f\u975e\u5e38\u6709\u5fc5\u8981\u7684\uff08\u771f\u662f\u8840\u4e0e\u6cea\u7684\u6559\u8bad<br>\u5199\u7684\u65f6\u5019\u5565\u4e5f\u6ca1\u7ba1\uff0c\u4e0a\u6765\u76f4\u63a5\u83bd\uff0c\u8d70\u4e86\u597d\u591a\u5f2f\u8defqwq\uff08\u7684\u786e\u6709\u5f88\u591a\u4f18\u5316\u65b9\u6cd5\u4e66\u4e2d\u5df2\u7ecf\u8bb2\u4e86ww<\/p>\n\n\n\n<p>\u5176\u5b9e\u4ee3\u7801\u8fd8\u662f\u6bd4\u8f83\u597d\u60f3\uff08\u5c31\u662fdebug\u81ea\u95ed\u4e86\u4ed6\u5927\u6982\u5360\u4e86\u621195%\u7684\u65f6\u95f4w<\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p><strong>\u5177\u4f53\u5b9e\u73b0<\/strong>\u5c31\u662f\u6211\u4eec\u8003\u8651\u60f3\u627ebestfit\uff0c\u90a3\u4e48\u8fd9\u4e2a\u5728\u94fe\u8868\u4e0a\u6700\u52a3O(n)?\uff08\u597d\u50cf\u4ec0\u4e48\u65b9\u6cd5\u90fd\u5fc5\u987b\u6700\u52a3O(n)\uff0c\u4f46\u4f3c\u4e4e\u6781\u96be\u5361\u6389qwq <br>\u90a3\u4e48\u6211\u4eec\u8003\u8651\u66f4\u4f18\u7684\u7a33\u5b9a\u505a\u6cd5\uff1a\u5e73\u8861\u6811\uff08treap\uff09\uff01\u6211\u4eec\u53ef\u4ee5\u7a33\u5b9a\u5728O(logn)\u65f6\u95f4\u5185\u627e\u5230\u540e\u7ee7\u8282\u70b9\u3002 <br>\u6211\u4eec\u57fa\u4e8e\u5e73\u8861\u6811\u53ef\u7ef4\u62a4\u63d2\u5165\u5220\u9664\u548c\u67e5\u627e\u7684\u6027\u8d28\uff0c\u5c06\u6bcf\u4e2afree\u5757\u90fd\u653e\u5165\u5e73\u8861\u6811\u4e2d\uff0c\u8fd9\u6837\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u67e5\u8be2\u548c\u53d6\u51fa \uff0c\u4f46\u662f\u6b64\u65f6\u4f1a\u6709\u975e\u5e38\u591a\u7684\u91cd\u590d\u5143\u7d20\uff0c\u4e00\u4e2a\u5f88\u7b80\u5355\u7684\u601d\u60f3\uff0c\u5c31\u53ef\u4ee5\u628a\u6240\u6709\u91cd\u590d\u5143\u7d20\u653e\u5230\u540c\u4e00\u4e2a\u70b9\u4e2d\uff0c\u7ef4\u62a4\u4e00\u4e2a\u94fe\u8868\uff0c\u5373\u5e73\u8861\u6811\u7ef4\u62a4\u5927\u5c0f\u4e3asize\u7684\u53cc\u5411\u94fe\u8868\u5934\u5373\u53ef <br>\u8fd9\u4e2a\u65f6\u5019\u6211\u4eec\u8003\u8651\u5220\u9664\u6307\u5b9a\u8282\u70b9\u5c31\u4e0d\u9700\u8981\u5728\u5e73\u8861\u6811\u4e0a\u5220\u9664\uff0c\u76f4\u63a5\u5728\u94fe\u8868\u5220\u9664\u5373\u53ef\uff0c\u9664\u975e\u94fe\u8868\u6e05\u7a7a\uff0c\u6211\u4eec\u518d\u5728\u5e73\u8861\u6811\u4e0a\u5220\u9664 <br>\u63d2\u5165\u540c\u7406\uff0c\u6211\u4eec\u53ea\u6709\u67e5\u8be2\u4e4b\u540e\u8be5\u70b9\u4e0d\u5b58\u5728\u624d\u5728\u5e73\u8861\u6811\u4e0a\u63d2\u5165\uff08\u8fd9\u6837\u7701\u4e86\u5f88\u591a\u5e38\u6570 <\/p>\n\n\n\n<p>\u90a3\u4e48\u8fd9\u65f6\u5019\u518d\u8003\u8651\u8fdb\u4e00\u6b65\u4f18\u5316\u65f6\u95f4\uff0c\u6211\u4eec\u8003\u8651\u5bf9\u5c0f\u6570\u636e\uff08\u8bbe\u7f6esize&lt;=80\uff09\u76f4\u63a5\u8bb0\u5f55\u5bf9\u5e94\u94fe\u8868\uff0c\u800c\u4e0d\u5b58\u5728\u7ebf\u6bb5\u6811\u4e2d \uff08\u56e0\u4e3a\u6211\u4eec\u5f88\u6709\u53ef\u80fd\u7ecf\u5e38\u4ea7\u751f\u548c\u5408\u5e76\u8fd9\u79cd\u5c0f\u788e\u7247 <\/p>\n\n\n\n<p>\u5bf9\u4e8e\u5e73\u8861\u6811\u91c7\u53d6\u5c3d\u91cf\u4e0d\u65cb\u8f6c\uff08\u8fd9\u6837\u7ea2\u9ed1\u6811\u53ef\u80fd\u4f1a\u66f4\u597d\uff1f\uff09\uff0c\u56e0\u4e3a\u6211\u4eec\u53d1\u73b0\u65cb\u8f6c\u7684\u4ee3\u4ef7\u8f83\u5927\uff0c\u5373\u8981\u66f4\u65b0\u7684\u4fe1\u606f\u8f83\u591a\uff08\u5b9e\u9645\u6d4b\u8bd5\u53cd\u800c\u66f4\u6162w <\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p> <strong>\u7b2c\u4e8c\u4e2a\u65f6\u95f4\u4f18\u5316<\/strong>\uff1a\u6211\u4eec\u53d1\u73b0\u9891\u7e41sbrk\u662f\u975e\u5e38\u8017\u65f6\u7684\uff0c\u90a3\u4e48\u6211\u4eec\u8003\u8651\u4e00\u6b21\u6269\u5c55\u4e00\u6bb5\u7a7a\u95f4\uff0c\u7136\u540e\u4e0d\u591f\u7528\u518d\u7ee7\u7eed\u6269\u5145 <\/p>\n\n\n\n<p>\u8fd9\u91cc\u6211\u4eec\u5747\u8861\u4e86\u65f6\u95f4\u548c\u7a7a\u95f4\uff0c\u53d1\u73b0400\u9644\u8fd1\u7684\u503c\u90fd\u8fd8\u884c\uff1f\uff08\u53ef\u80fd\u662f\u6211\u5e73\u8861\u6811\u5e38\u6570\u592a\u5927\u4e86\u545c\u545c\u545c <\/p>\n\n\n\n<p>\uff08\u4e00\u4e2amagic number\uff1a\u5bf9\u4e8e\u6570\u636e\u4e00\u4e2a\u6d4b\u8bd5\u70b9\u628a448\u53d8\u6210512\u6548\u679c\u6781\u4f73\uff1f<\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p><strong> \u7a7a\u95f4\u7684\u4f18\u5316<\/strong>\uff1a <\/p>\n\n\n\n<p>\u6211\u4eec\u9996\u5148\u53d1\u73b0\u5185\u5b58\u662f\u5c0f\u4e8e2^32\u5b57\u8282\u7684\uff0c\u90a3\u4e48\u4e5f\u5c31\u662f\u8bf4\u6211\u4eec\u5b8c\u5168\u53ef\u4ee5\u53ea\u5b58\u504f\u79fb\u91cf\u5373\u53ef\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u5c06\u5730\u5740\u538b\u7f29\u4e3a4\u5b57\u8282 <br>\u5176\u6b21\u53c2\u8003csapp\u4e66\u4e2d\u8bb2\u89e3\uff0cfooter\u662f\u53ef\u4ee5\u541e\u6389\u7684\uff08\u5373\u6211\u4eec\u5229\u7528header\u50a8\u5b58\u524d\u4e00\u5757\u662f\u5426use\uff09\uff0c\u4ee5\u53ca\u548cheader\u5171\u75288\u5b57\u8282\u5bf9\u9f50 <\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p><strong>\u5408\u5e76\u7a7a\u95f2\u5757<\/strong>\uff1a\u6211\u4eec\u5bf9\u4e8e\u6bcf\u6b21add\u64cd\u4f5c\uff08\u5373\u4ea7\u751f\u65b0\u7684\u7a7a\u95f2\u5757\uff09\u90fd\u5c1d\u8bd5\u5408\u5e76\u76f8\u90bb\u7684\u5757\uff0c\uff08\u6211\u4eec\u8fd9\u91cc\u53ea\u8003\u8651\u524d\u4e00\u5757\u548c\u540e\u4e00\u5757\uff09\u5982\u679c\u80fd\u5408\u5e76\u5219\u5408\u5e76\u5728\u4e00\u8d77\u518d\u6267\u884cadd\u64cd\u4f5c<\/p>\n\n\n\n<p><strong>\u5339\u914d\u540e\u5206\u5272\uff1a<\/strong>\u6211\u4eec\u5bf9\u4e8ebestfit\u4e4b\u540e\u53ef\u80fd\u4f1a\u6709\u591a\u4f59\u7a7a\u95f2\u5757\uff0c\u90a3\u4e48\u6211\u4eec\u5bf9\u4e8e&gt;8\u5b57\u8282\u7684\u5757\u76f4\u63a5\u63d2\u5165\u7ef4\u62a4\u7684\u4fe1\u606f\u4e4b\u4e2d\uff0c\u90a3\u4e48\u6211\u4eec\u5bf9\u4e8e8\u5b57\u8282\u7684\u5757\u76f4\u63a5\u4fdd\u5b58\u539f\u4f4d\uff0c\u7b49\u5f85\u4e4b\u540e\u7684\u5408\u5e76\u64cd\u4f5c\u5373\u53ef<\/p>\n\n\n\n<p>\u4e00\u4e2a\u5c0f\u4f18\u5316\uff1a\u6bcf\u6b21\u65b0sbrk\u5224\u4e00\u4e0b\u524d\u9762\u5757\u662f\u4e0d\u662ffree\uff08\u52a0\u4e0a\u8fd9\u4e2a\u5c31\u6ee1\u4e86\uff1fqwq<\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p> <\/p>\n\n\n\n<p><strong>\u5177\u4f53\u4fe1\u606f\u5b58\u50a8<\/strong>\uff1a <\/p>\n\n\n\n<p><strong>\u5206\u914d\u5757<\/strong>\uff1a<\/p>\n\n\n\n<p>\u6211\u4eec\u5bf9\u4e8e\u5934\u90e84\u5b57\u8282\u5b58\u50a8\u4fe1\u606f\uff0c\u5373\u4e3a \uff08\u5757\u5927\u5c0f(size)|preUSE(0x2 or 0x0)|USE(0x1)\uff09\uff0c \u56e0\u4e3a\u6211\u4eec\u4fdd\u8bc1\u4e86\u6570\u636e8\u5b57\u8282\u5bf9\u9f50\uff0c\u56e0\u6b64\u5757\u5927\u5c0f\u540e\u4e09\u4f4d\u5fc5\u4e3a0\uff0c\u56e0\u6b64\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u6765\u5b58\u50a8\u4fe1\u606f <\/p>\n\n\n\n<p><strong>\u7a7a\u95f2\u5757<\/strong>\uff1a <\/p>\n\n\n\n<p>\u5934\u90e84\u5b57\u8282\u4fe1\u606f\u4e3a \uff08\u5757\u5927\u5c0f(size)|preUSE(0x2 or 0x0)|USE(0x0)\uff09\uff0c\u5c3e\u90e84\u5b57\u8282\u4fe1\u606f\u4e3a\u6307\u5411\u5934\u90e8\u7684\u6307\u9488\u7684\u504f\u79fb\u91cf <br>\u4e2d\u95f4\u4fe1\u606f\u5206\u4e3a\u4e24\u5927\u7c7b\uff1a\uff08\u4ee5\u4e0b\u6bcf\u4e00\u5757\u4e3a4\u5b57\u8282(\u4ee5\u201d|\u201c\u5206\u5272)\uff0c\u4ece\u5934\u90e8\u4e4b\u540e\u5f00\u59cb\u8fde\u7eed\u7a7a\u95f4\uff0c\u4ee5\u4e0b\u4e0d\u7279\u6b8a\u8bf4\u660e\u6240\u6709\u6307\u9488\u5168\u4e3a\u504f\u79fb\u91cf\uff09 <\/p>\n\n\n\n<p> 1\uff09fastbin(size&lt;=80)\uff1a <br>\u5bf9\u5e94\u94fe\u8868pre\u6307\u9488 | \u5bf9\u5e94\u94fe\u8868next\u6307\u9488<\/p>\n\n\n\n<p> 2\uff09largebin(size&gt;80): <br>     1.\u5e73\u8861\u6811\u8282\u70b9\uff1a\uff08\u6ce8\uff1arand\u540e\u6765\u53d6\u6d88\u8bbe\u4e3a0\u4e86\uff09 <br>        \u5e73\u8861\u6811\u968f\u673arand | \u8282\u70b9\u5de6\u513f\u5b50\u6307\u9488 | \u8282\u70b9\u53f3\u513f\u5b50\u6307\u9488 | \u5bf9\u5e94\u94fe\u8868pre | \u5bf9\u5e94\u94fe\u8868next | \u5e73\u8861\u6811\u4e0a\u7684\u7236\u4eb2\u6307\u9488 <br>     2.\u5bf9\u5e94\u94fe\u8868\u8282\u70b9\uff1a <br>         \u7a7a | \u7a7a | \u7a7a | \u5bf9\u5e94\u94fe\u8868pre | \u5bf9\u5e94\u94fe\u8868next | \u7a7a <\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"763\" src=\"https:\/\/kylelv.com\/wp-content\/uploads\/2020\/12\/image-4-1024x763.png\" alt=\"\" class=\"wp-image-793\" srcset=\"https:\/\/blog.kylelv.com\/wp-content\/uploads\/2020\/12\/image-4-1024x763.png 1024w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2020\/12\/image-4-300x224.png 300w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2020\/12\/image-4-768x573.png 768w, https:\/\/blog.kylelv.com\/wp-content\/uploads\/2020\/12\/image-4.png 1210w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>\u611f\u89c9\u597d\u50cf\u6ca1\u600e\u4e48\u5199\u8fc7lab\uff0c\u4e00\u65b9\u9762\u662f\u4e4b\u524dlab\u4e5f\u6ca1\u5565\u597d\u5199\u7684\uff0c\u53e6\u4e00\u65b9\u9762\u4e5f\u662f\u5927\u6982\u8001\u5e08\u4e5f\u4e0d\u8ba9\u5916\u4f20\u3002\u3002 \u56e0\u6b64\u5bf9\u4e8emall [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[86,85],"class_list":["post-780","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-lab","tag-malloc"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/780","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=780"}],"version-history":[{"count":8,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/780\/revisions"}],"predecessor-version":[{"id":831,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/780\/revisions\/831"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}