From patchwork Fri Jul 7 12:12:45 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tahsin Erdogan X-Patchwork-Id: 785456 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3x3tmB6wRlz9s7v for ; Fri, 7 Jul 2017 22:12:58 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=google.com header.i=@google.com header.b="r9qr9HmR"; dkim-atps=neutral Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751921AbdGGMM4 (ORCPT ); Fri, 7 Jul 2017 08:12:56 -0400 Received: from mail-pf0-f180.google.com ([209.85.192.180]:36512 "EHLO mail-pf0-f180.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750892AbdGGMMz (ORCPT ); Fri, 7 Jul 2017 08:12:55 -0400 Received: by mail-pf0-f180.google.com with SMTP id q86so16374583pfl.3 for ; Fri, 07 Jul 2017 05:12:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=o6dOkMxyNw1aaDG7WCQRVLo9LvTiD9X7D+TG8a0sbZ8=; b=r9qr9HmRgAo6gKx6EfQ88idV40utu/xw1SH3YC9MXIt9GYyRqJBK27wbo455quV4bG EhbJs9ubTu0adS2KONWVWU9+CpucMm/ec2/Q+tZAHTRmeJHWcvNJr4xVbHcMjm/kTxoj pRIbe1TcxirQWzNVVI6aO9R4kpRkznTQSv8CH3XghUkrJ5phUnT84JQF+SYCy62xCkEK njkcTBtzIJe5ILmxUoMlCKSXpANNR9Xbsw+EMNpMs88yrsBWHb/+KtyHVkgZquKsKC27 iebU1jnve9o4PUvu5HEOLPJ3hpdbcJPUQjvmRIfGMmUfmM9jyaPh/SDYUY04sYe1T3C1 wB2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=o6dOkMxyNw1aaDG7WCQRVLo9LvTiD9X7D+TG8a0sbZ8=; b=N2rWR7DS74V4CTRDzLLW59mMphB15jyNNDoRhLa3/RPJq+2eI2JD401wrksniHf01g JiQLTNiv3FmivuyBH2Fl03IEZbOq9EQKW4iWiivJyVOk580zEuekldXcHcXco6XMyCNG ypqDAnVjc9W8dFzSl2U3VCedf4XKR5xHj8PLLRhroxlG7eLWmEpfSmaJaogPX/7bgikh /b2sA8K1uQJflnudX9sNHNsLkv58+CQnhlJaHiUNdZxtdl8p6rLdzbJqxkW39krqmex+ d+36VD0on/WiIuUQE5Dg1eyjxeWewYqfgHR3YJyfJuNHgNA+1Xw58Ocy53+ZU2GAxXRp IhLw== X-Gm-Message-State: AIVw110IFw3DdfiviDZoPRBrR6pYJpZSHjihcleEkmyriYRW3dqCuY/b wgAcvRs7GegDIPJb X-Received: by 10.99.18.65 with SMTP id 1mr1158809pgs.132.1499429574261; Fri, 07 Jul 2017 05:12:54 -0700 (PDT) Received: from tahsin1.svl.corp.google.com ([100.123.230.167]) by smtp.gmail.com with ESMTPSA id c62sm5589357pfb.93.2017.07.07.05.12.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 07 Jul 2017 05:12:53 -0700 (PDT) From: Tahsin Erdogan To: Andreas Dilger , "Darrick J . Wong" , Theodore Ts'o , linux-ext4@vger.kernel.org Cc: Tahsin Erdogan Subject: [PATCH 3/4] libext2fs: eliminate empty element holes in ext2_xattr_handle->attrs Date: Fri, 7 Jul 2017 05:12:45 -0700 Message-Id: <20170707121246.6159-3-tahsin@google.com> X-Mailer: git-send-email 2.13.2.725.g09c95d1e9-goog In-Reply-To: <20170707121246.6159-1-tahsin@google.com> References: <20170707121246.6159-1-tahsin@google.com> Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org When an extended attribute is removed, its array element is emptied. This creates holes in the array so various places that want to walk filled elements have to do an empty element check. Have remove operation shift remaining filled elements to the left. This allows a simple iteration up to ext2_xattr_handle->count to walk all filled entries, and so empty element checks become unnecessary. Signed-off-by: Tahsin Erdogan --- lib/ext2fs/ext_attr.c | 93 ++++++++++++++++----------------------------------- 1 file changed, 29 insertions(+), 64 deletions(-) diff --git a/lib/ext2fs/ext_attr.c b/lib/ext2fs/ext_attr.c index 2e9fc96d114d..00ff79ae3890 100644 --- a/lib/ext2fs/ext_attr.c +++ b/lib/ext2fs/ext_attr.c @@ -335,7 +335,7 @@ static struct ea_name_index ea_names[] = { static int find_ea_index(char *fullname, char **name, int *index); -/* Push empty attributes to the end and inlinedata to the front. */ +/* Pull inlinedata to the front. */ static int attr_compare(const void *a, const void *b) { const struct ext2_xattr *xa = a, *xb = b; @@ -343,11 +343,7 @@ static int attr_compare(const void *a, const void *b) int xa_idx, xb_idx; int cmp; - if (xa->name == NULL) - return +1; - else if (xb->name == NULL) - return -1; - else if (!strcmp(xa->name, "system.data")) + if (!strcmp(xa->name, "system.data")) return -1; else if (!strcmp(xb->name, "system.data")) return +1; @@ -675,10 +671,7 @@ static errcode_t write_xattrs_to_buffer(struct ext2_xattr_handle *handle, memset(entries_start, 0, storage_size); /* For all remaining x... */ - for (; x < handle->attrs + handle->capacity; x++) { - if (!x->name) - continue; - + for (; x < handle->attrs + handle->count; x++) { /* Calculate index and shortname position */ shortname = x->name; ret = find_ea_index(x->name, &shortname, &idx); @@ -766,12 +759,9 @@ errcode_t ext2fs_xattrs_write(struct ext2_xattr_handle *handle) goto out; } - /* - * Force the inlinedata attr to the front and the empty entries - * to the end. - */ + /* Force the inlinedata attr to the front. */ x = handle->attrs; - qsort(x, handle->capacity, sizeof(struct ext2_xattr), attr_compare); + qsort(x, handle->count, sizeof(struct ext2_xattr), attr_compare); /* Does the inode have space for EA? */ if (inode->i_extra_isize < sizeof(inode->i_extra_isize) || @@ -813,7 +803,7 @@ write_ea_block: if (err) goto out2; - if (x < handle->attrs + handle->capacity) { + if (x < handle->attrs + handle->count) { err = EXT2_ET_EA_NO_SPACE; goto out2; } @@ -865,8 +855,7 @@ static errcode_t read_xattrs_from_buffer(struct ext2_xattr_handle *handle, struct ext2_inode_large *inode, struct ext2_ext_attr_entry *entries, unsigned int storage_size, - char *value_start, - size_t *nr_read) + char *value_start) { struct ext2_xattr *x; struct ext2_ext_attr_entry *entry, *end; @@ -876,10 +865,6 @@ static errcode_t read_xattrs_from_buffer(struct ext2_xattr_handle *handle, unsigned int values_size = storage_size + ((char *)entries - value_start); - x = handle->attrs; - while (x->name) - x++; - /* find the end */ end = entries; remain = storage_size; @@ -904,13 +889,14 @@ static errcode_t read_xattrs_from_buffer(struct ext2_xattr_handle *handle, !EXT2_EXT_IS_LAST_ENTRY(entry)) { /* Allocate space for more attrs? */ - if (x == handle->attrs + handle->capacity) { + if (handle->count == handle->capacity) { err = ext2fs_xattrs_expand(handle, 4); if (err) return err; - x = handle->attrs + handle->capacity - 4; } + x = handle->attrs + handle->count; + /* header eats this space */ remain -= sizeof(struct ext2_ext_attr_entry); @@ -1013,8 +999,7 @@ static errcode_t read_xattrs_from_buffer(struct ext2_xattr_handle *handle, } } - x++; - (*nr_read)++; + handle->count++; entry = EXT2_EXT_ATTR_NEXT(entry); } @@ -1084,8 +1069,8 @@ errcode_t ext2fs_xattrs_read(struct ext2_xattr_handle *handle) inode->i_extra_isize + sizeof(__u32); err = read_xattrs_from_buffer(handle, inode, - (struct ext2_ext_attr_entry *) start, storage_size, - start, &handle->count); + (struct ext2_ext_attr_entry *) start, + storage_size, start); if (err) goto out; } @@ -1121,8 +1106,8 @@ read_ea_block: sizeof(struct ext2_ext_attr_header); start = block_buf + sizeof(struct ext2_ext_attr_header); err = read_xattrs_from_buffer(handle, inode, - (struct ext2_ext_attr_entry *) start, storage_size, - block_buf, &handle->count); + (struct ext2_ext_attr_entry *) start, + storage_size, block_buf); if (err) goto out3; @@ -1149,10 +1134,7 @@ errcode_t ext2fs_xattrs_iterate(struct ext2_xattr_handle *h, int ret; EXT2_CHECK_MAGIC(h, EXT2_ET_MAGIC_EA_HANDLE); - for (x = h->attrs; x < h->attrs + h->capacity; x++) { - if (!x->name) - continue; - + for (x = h->attrs; x < h->attrs + h->count; x++) { ret = func(x->name, x->value, x->value_len, data); if (ret & XATTR_CHANGED) h->dirty = 1; @@ -1171,8 +1153,8 @@ errcode_t ext2fs_xattr_get(struct ext2_xattr_handle *h, const char *key, errcode_t err; EXT2_CHECK_MAGIC(h, EXT2_ET_MAGIC_EA_HANDLE); - for (x = h->attrs; x < h->attrs + h->capacity; x++) { - if (!x->name || strcmp(x->name, key)) + for (x = h->attrs; x < h->attrs + h->count; x++) { + if (strcmp(x->name, key)) continue; if (!(h->flags & XATTR_HANDLE_FLAG_RAW) && @@ -1260,12 +1242,11 @@ errcode_t ext2fs_xattr_set(struct ext2_xattr_handle *handle, const void *value, size_t value_len) { - struct ext2_xattr *x, *last_empty; + struct ext2_xattr *x; char *new_value; errcode_t err; EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EA_HANDLE); - last_empty = NULL; err = ext2fs_get_mem(value_len, &new_value); if (err) @@ -1280,12 +1261,7 @@ errcode_t ext2fs_xattr_set(struct ext2_xattr_handle *handle, } else memcpy(new_value, value, value_len); - for (x = handle->attrs; x < handle->attrs + handle->capacity; x++) { - if (!x->name) { - last_empty = x; - continue; - } - + for (x = handle->attrs; x < handle->attrs + handle->count; x++) { /* Replace xattr */ if (strcmp(x->name, key) == 0) { ext2fs_free_mem(&x->value); @@ -1296,25 +1272,15 @@ errcode_t ext2fs_xattr_set(struct ext2_xattr_handle *handle, } } - /* Add attr to empty slot */ - if (last_empty) { - err = ext2fs_get_mem(strlen(key) + 1, &last_empty->name); + if (handle->count == handle->capacity) { + /* Expand array, append slot */ + err = ext2fs_xattrs_expand(handle, 4); if (err) goto errout; - strcpy(last_empty->name, key); - last_empty->value = new_value; - last_empty->value_len = value_len; - handle->dirty = 1; - handle->count++; - return 0; - } - /* Expand array, append slot */ - err = ext2fs_xattrs_expand(handle, 4); - if (err) - goto errout; + x = handle->attrs + handle->capacity - 4; + } - x = handle->attrs + handle->capacity - 4; err = ext2fs_get_mem(strlen(key) + 1, &x->name); if (err) goto errout; @@ -1337,16 +1303,15 @@ errcode_t ext2fs_xattr_remove(struct ext2_xattr_handle *handle, const char *key) { struct ext2_xattr *x; + struct ext2_xattr *end = handle->attrs + handle->count; EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EA_HANDLE); - for (x = handle->attrs; x < handle->attrs + handle->capacity; x++) { - if (!x->name) - continue; - + for (x = handle->attrs; x < end; x++) { if (strcmp(x->name, key) == 0) { ext2fs_free_mem(&x->name); ext2fs_free_mem(&x->value); - x->value_len = 0; + memmove(x, x + 1, (char *)end - (char *)(x + 1)); + memset(end, 0, sizeof(*end)); handle->dirty = 1; handle->count--; return 0;