Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Mon, 4 Jan 2021 02:25:54 +0200
From:   Kari Argillander <kari.argillander@gmail.com>
To:     Konstantin Komarov <almaz.alexandrovich@paragon-software.com>
Cc:     linux-fsdevel@vger.kernel.org, viro@zeniv.linux.org.uk,
        linux-kernel@vger.kernel.org, pali@kernel.org, dsterba@suse.cz,
        aaptel@suse.com, willy@infradead.org, rdunlap@infradead.org,
        joe@perches.com, mark@harmstone.com, nborisov@suse.com,
        linux-ntfs-dev@lists.sourceforge.net, anton@tuxera.com,
        dan.carpenter@oracle.com, hch@lst.de, ebiggers@kernel.org,
        andy.lavr@gmail.com
Subject: Re: [PATCH v17 05/10] fs/ntfs3: Add attrib operations
Message-ID: <20210104002554.gdxoyu2q2aaae5ph@kari-VirtualBox>
References: <20201231152401.3162425-1-almaz.alexandrovich@paragon-software.com>
 <20201231152401.3162425-6-almaz.alexandrovich@paragon-software.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20201231152401.3162425-6-almaz.alexandrovich@paragon-software.com>
Precedence: bulk

On Thu, Dec 31, 2020 at 06:23:56PM +0300, Konstantin Komarov wrote:
> This adds attrib operations
> 
> Signed-off-by: Konstantin Komarov <almaz.alexandrovich@paragon-software.com>
> ---
>  fs/ntfs3/attrib.c   | 2081 +++++++++++++++++++++++++++++++++++++++++++
>  fs/ntfs3/attrlist.c |  463 ++++++++++
>  fs/ntfs3/xattr.c    | 1072 ++++++++++++++++++++++
>  3 files changed, 3616 insertions(+)
>  create mode 100644 fs/ntfs3/attrib.c
>  create mode 100644 fs/ntfs3/attrlist.c
>  create mode 100644 fs/ntfs3/xattr.c
> 
> diff --git a/fs/ntfs3/attrlist.c b/fs/ntfs3/attrlist.c

> +/*
> + * al_find_ex
> + *
> + * finds the first le in the list which matches type, name and vcn
> + * Returns NULL if not found
> + */
> +struct ATTR_LIST_ENTRY *al_find_ex(struct ntfs_inode *ni,
> +				   struct ATTR_LIST_ENTRY *le,
> +				   enum ATTR_TYPE type, const __le16 *name,
> +				   u8 name_len, const CLST *vcn)
> +{
> +	struct ATTR_LIST_ENTRY *ret = NULL;
> +	u32 type_in = le32_to_cpu(type);
> +
> +	while ((le = al_enumerate(ni, le))) {
> +		u64 le_vcn;
> +		int diff;
> +
> +		/* List entries are sorted by type, name and vcn */

Isn't name sorted with upcase sort.

> +		diff = le32_to_cpu(le->type) - type_in;
> +		if (diff < 0)
> +			continue;
> +
> +		if (diff > 0)
> +			return ret;
> +
> +		if (le->name_len != name_len)
> +			continue;
> +
> +		if (name_len &&
> +		    memcmp(le_name(le), name, name_len * sizeof(short)))
> +			continue;

So does this compare name correctly? So it is caller responsible that
name is up_cased? Or does it even mater.

And this will check every name in right type. Why not use name_cmp and
then we know if we over. It might be because performance. But maybe
we can check that like every 10 iteration or something.

> +		if (!vcn)
> +			return le;
> +
> +		le_vcn = le64_to_cpu(le->vcn);
> +		if (*vcn == le_vcn)
> +			return le;
> +
> +		if (*vcn < le_vcn)
> +			return ret;
> +
> +		ret = le;

So we still have wrong vcn at this point. And we save that so we can
return it. What happens if we will not found right one. Atlest function 
comment say that we should return NULL if we do not found matching entry.

> +	}
> +
> +	return ret;
> +}
> +
> +/*
> + * al_find_le_to_insert
> + *
> + * finds the first list entry which matches type, name and vcn

This comment seems wrong? This seems to find insert point for new
le.

> + * Returns NULL if not found
> + */
> +static struct ATTR_LIST_ENTRY *
> +al_find_le_to_insert(struct ntfs_inode *ni, enum ATTR_TYPE type,
> +		     const __le16 *name, u8 name_len, const CLST *vcn)
> +{
> +	struct ATTR_LIST_ENTRY *le = NULL, *prev;
> +	u32 type_in = le32_to_cpu(type);
> +	int diff;
> +
> +	/* List entries are sorted by type, name, vcn */
> +next:
> +	le = al_enumerate(ni, prev = le);
> +	if (!le)
> +		goto out;
> +	diff = le32_to_cpu(le->type) - type_in;
> +	if (diff < 0)
> +		goto next;
> +	if (diff > 0)
> +		goto out;
> +
> +	if (ntfs_cmp_names(name, name_len, le_name(le), le->name_len, NULL) > 0)
> +		goto next;

Why not go out if compare is < 0. In my mind this will totally ignore
name and next just find right vcn (or we come next ID) and call it a day. 

NAME	VCN
[AAB]	[2] <- Looks insert point for this.

[AAA]	[1]
[AAB]	[1]
	    <- This is right point.
[AAC]	[1]
	    <- But we tell that insert point is here.
[AAD]	[2]

I might be totally wrong but please tell me what I'm missing.

> +	if (!vcn || *vcn > le64_to_cpu(le->vcn))
> +		goto next;
> +
> +out:
> +	if (!le)
> +		le = prev ? Add2Ptr(prev, le16_to_cpu(prev->size)) :
> +			    ni->attr_list.le;
> +
> +	return le;
> +}

There seems to be lot of linear list search. Do you think it will be
benefital to code binary or jump search for them? Just asking for
intrest. Might be that it will not benefit at all but just thinking
here.

I might try to do that in some point if someone see point of that.