<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:DengXian;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:DengXian;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
text-align:justify;
text-justify:inter-ideograph;
font-size:10.5pt;
font-family:DengXian;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
.MsoChpDefault
{mso-style-type:export-only;}
/* Page Definitions */
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="ZH-CN" link="blue" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US">Hi all,</span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">This is my first time sending patches by email. If something is not properly done, please point it out.</span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I have a question for now: How am I supposed to submit patches to erofs-utils now? Some E-mail address listed in AUTHORS and README seems no longer valid (email to
<a href="mailto:gaoxiang25@huawei.com">gaoxiang25@huawei.com</a> was rejected). Is it enough to post the patches to this mailing list? I added all addresses in README, but I got a message said my email is rejected. I’m not sure who actually received my email.</span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:12.0pt;font-family:SimSun"><o:p> </o:p></span></p>
<div style="mso-element:para-border-div;border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="border:none;padding:0cm"><b>发件人<span lang="EN-US">: </span>
</b><span lang="EN-US"><a href="mailto:huww98@outlook.com"><span lang="EN-US"><span lang="EN-US">胡</span></span><span lang="EN-US"><span lang="EN-US">
</span></span><span lang="EN-US"><span lang="EN-US">玮文</span></span></a><br>
</span><b>发送时间<span lang="EN-US">: </span></b><span lang="EN-US">2021</span>年<span lang="EN-US">1</span>月<span lang="EN-US">1</span>日<span lang="EN-US"> 17:16<br>
</span><b>收件人<span lang="EN-US">: </span></b><span lang="EN-US"><a href="mailto:bluce.liguifu@huawei.com">Li Guifu</a>;
<a href="mailto:miaoxie@huawei.com">Miao Xie</a>; <a href="mailto:fangwei1@huawei.com">
Fang Wei</a><br>
</span><b>抄送<span lang="EN-US">: </span></b><span lang="EN-US"><a href="mailto:gaoxiang25@huawei.com">Gao Xiang</a>;
<a href="mailto:yuchao0@huawei.com">Chao Yu</a>; <a href="mailto:linux-erofs@lists.ozlabs.org">
linux-erofs@lists.ozlabs.org</a>; <a href="mailto:huww98@outlook.com"><span lang="EN-US"><span lang="EN-US">胡玮文</span></span></a><br>
</span><b>主题<span lang="EN-US">: </span></b><span lang="EN-US">[PATCH 1/2] erofs-utils: optimize mkfs to O(N), N = #files</span></p>
</div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:12.0pt;font-family:SimSun"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span lang="EN-US" style="font-size:11.0pt">When using EROFS to pack our dataset which consists of millions of<br>
files, mkfs.erofs is very slow compared with mksquashfs.<br>
<br>
The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which<br>
iterate over all previously allocated buffer blocks, making the<br>
complexity of the algrithm O(N^2) where N is the number of files.<br>
<br>
With this patch:<br>
<br>
* global `last_mapped_block` is mantained to avoid full scan in<br>
`erofs_mapbh` function.<br>
<br>
* global `non_full_buffer_blocks` mantains a list of buffer block for<br>
each type and each possible remaining bytes in the block. Then it is<br>
used to identify the most suitable blocks in future `erofs_balloc`,<br>
avoiding full scan.<br>
<br>
Some new data structure is allocated in this patch, more RAM usage is<br>
expected, but not much. When I test it with ImageNet dataset (1.33M<br>
files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is<br>
spent on IO.<br>
<br>
Signed-off-by: Hu Weiwen <huww98@outlook.com><br>
---<br>
lib/cache.c | 102 +++++++++++++++++++++++++++++++++++++++++++++-------<br>
1 file changed, 89 insertions(+), 13 deletions(-)<br>
<br>
diff --git a/lib/cache.c b/lib/cache.c<br>
index 0d5c4a5..3412a0b 100644<br>
--- a/lib/cache.c<br>
+++ b/lib/cache.c<br>
@@ -18,6 +18,18 @@ static struct erofs_buffer_block blkh = {<br>
};<br>
static erofs_blk_t tail_blkaddr;<br>
<br>
+/**<br>
+ * Some buffers are not full, we can reuse it to store more data<br>
+ * 2 for DATA, META<br>
+ * EROFS_BLKSIZ for each possible remaining bytes in the last block<br>
+ **/<br>
+static struct erofs_buffer_block_record {<br>
+ struct list_head list;<br>
+ struct erofs_buffer_block *bb;<br>
+} non_full_buffer_blocks[2][EROFS_BLKSIZ];<br>
+<br>
+static struct erofs_buffer_block *last_mapped_block = &blkh;<br>
+<br>
static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)<br>
{<br>
return erofs_bh_flush_generic_end(bh);<br>
@@ -62,6 +74,12 @@ struct erofs_bhops erofs_buf_write_bhops = {<br>
/* return buffer_head of erofs super block (with size 0) */<br>
struct erofs_buffer_head *erofs_buffer_init(void)<br>
{<br>
+ for (int i = 0; i < 2; i++) {<br>
+ for (int j = 0; j < EROFS_BLKSIZ; j++) {<br>
+ init_list_head(&non_full_buffer_blocks[i][j].list);<br>
+ }<br>
+ }<br>
+<br>
struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);<br>
<br>
if (IS_ERR(bh))<br>
@@ -131,7 +149,8 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,<br>
{<br>
struct erofs_buffer_block *cur, *bb;<br>
struct erofs_buffer_head *bh;<br>
- unsigned int alignsize, used0, usedmax;<br>
+ unsigned int alignsize, used0, usedmax, total_size;<br>
+ struct erofs_buffer_block_record * reusing = NULL;<br>
<br>
int ret = get_alignsize(type, &type);<br>
<br>
@@ -143,7 +162,38 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,<br>
usedmax = 0;<br>
bb = NULL;<br>
<br>
- list_for_each_entry(cur, &blkh.list, list) {<br>
+ erofs_dbg("balloc size=%lu alignsize=%u used0=%u", size, alignsize, used0);<br>
+ if (used0 == 0 || alignsize == EROFS_BLKSIZ) {<br>
+ goto alloc;<br>
+ }<br>
+ total_size = size + required_ext + inline_ext;<br>
+ if (total_size < EROFS_BLKSIZ) {<br>
+ // Try find a most fit block.<br>
+ DBG_BUGON(type < 0 || type > 1);<br>
+ struct erofs_buffer_block_record *non_fulls = non_full_buffer_blocks[type];<br>
+ for (struct erofs_buffer_block_record *r = non_fulls + round_up(total_size, alignsize);<br>
+ r < non_fulls + EROFS_BLKSIZ; r++) {<br>
+ if (!list_empty(&r->list)) {<br>
+ struct erofs_buffer_block_record *reuse_candidate =<br>
+ list_first_entry(&r->list, struct erofs_buffer_block_record, list);<br>
+ ret = __erofs_battach(reuse_candidate->bb, NULL, size, alignsize,<br>
+ required_ext + inline_ext, true);<br>
+ if (ret >= 0) {<br>
+ reusing = reuse_candidate;<br>
+ bb = reuse_candidate->bb;<br>
+ usedmax = (ret + required_ext) % EROFS_BLKSIZ + inline_ext;<br>
+ }<br>
+ break;<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ /* Try reuse last ones, which are not mapped and can be extended */<br>
+ cur = last_mapped_block;<br>
+ if (cur == &blkh) {<br>
+ cur = list_next_entry(cur, list);<br>
+ }<br>
+ for (; cur != &blkh; cur = list_next_entry(cur, list)) {<br>
unsigned int used_before, used;<br>
<br>
used_before = cur->buffers.off % EROFS_BLKSIZ;<br>
@@ -175,22 +225,32 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,<br>
continue;<br>
<br>
if (usedmax < used) {<br>
+ reusing = NULL;<br>
bb = cur;<br>
usedmax = used;<br>
}<br>
}<br>
<br>
if (bb) {<br>
+ erofs_dbg("reusing buffer. usedmax=%u", usedmax);<br>
bh = malloc(sizeof(struct erofs_buffer_head));<br>
if (!bh)<br>
return ERR_PTR(-ENOMEM);<br>
+ if (reusing) {<br>
+ list_del(&reusing->list);<br>
+ free(reusing);<br>
+ }<br>
goto found;<br>
}<br>
<br>
+alloc:<br>
/* allocate a new buffer block */<br>
- if (used0 > EROFS_BLKSIZ)<br>
+ if (used0 > EROFS_BLKSIZ) {<br>
+ erofs_dbg("used0 > EROFS_BLKSIZ");<br>
return ERR_PTR(-ENOSPC);<br>
+ }<br>
<br>
+ erofs_dbg("new buffer block");<br>
bb = malloc(sizeof(struct erofs_buffer_block));<br>
if (!bb)<br>
return ERR_PTR(-ENOMEM);<br>
@@ -211,6 +271,16 @@ found:<br>
required_ext + inline_ext, false);<br>
if (ret < 0)<br>
return ERR_PTR(ret);<br>
+ if (ret != 0) {<br>
+ /* This buffer is not full yet, we may reuse it */<br>
+ reusing = malloc(sizeof(struct erofs_buffer_block_record));<br>
+ if (!reusing) {<br>
+ return ERR_PTR(-ENOMEM);<br>
+ }<br>
+ reusing->bb = bb;<br>
+ list_add_tail(&reusing->list,<br>
+ &non_full_buffer_blocks[type][EROFS_BLKSIZ - ret - inline_ext].list);<br>
+ }<br>
return bh;<br>
}<br>
<br>
@@ -247,8 +317,10 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)<br>
{<br>
erofs_blk_t blkaddr;<br>
<br>
- if (bb->blkaddr == NULL_ADDR)<br>
+ if (bb->blkaddr == NULL_ADDR) {<br>
bb->blkaddr = tail_blkaddr;<br>
+ last_mapped_block = bb;<br>
+ }<br>
<br>
blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);<br>
if (blkaddr > tail_blkaddr)<br>
@@ -259,15 +331,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)<br>
<br>
erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb, bool end)<br>
{<br>
- struct erofs_buffer_block *t, *nt;<br>
-<br>
- if (!bb || bb->blkaddr == NULL_ADDR) {<br>
- list_for_each_entry_safe(t, nt, &blkh.list, list) {<br>
- if (!end && (t == bb || nt == &blkh))<br>
- break;<br>
- (void)__erofs_mapbh(t);<br>
- if (end && t == bb)<br>
- break;<br>
+ DBG_BUGON(!end);<br>
+ struct erofs_buffer_block *t = last_mapped_block;<br>
+ while (1) {<br>
+ t = list_next_entry(t, list);<br>
+ if (t == &blkh) {<br>
+ break;<br>
+ }<br>
+ (void)__erofs_mapbh(t);<br>
+ if (t == bb) {<br>
+ break;<br>
}<br>
}<br>
return tail_blkaddr;<br>
@@ -334,6 +407,9 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)<br>
if (!list_empty(&bb->buffers.list))<br>
return;<br>
<br>
+ if (bb == last_mapped_block) {<br>
+ last_mapped_block = list_prev_entry(bb, list);<br>
+ }<br>
list_del(&bb->list);<br>
free(bb);<br>
<br>
-- <br>
2.30.0<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:12.0pt;font-family:SimSun"><o:p> </o:p></span></p>
</div>
</body>
</html>