// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2017-2018 HUAWEI, Inc.
 *             https://www.huawei.com/
 * Copyright (C) 2022, Alibaba Cloud
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/dirent.h>
#include <sys/kernel.h>
#include <sys/libkern.h>
#include <sys/malloc.h>
#include <sys/namei.h>
#include <sys/proc.h>
#include <sys/stat.h>
#include <sys/vnode.h>

#include "internal.h"

struct erofs_qstr {
	const unsigned char *name;
	const unsigned char *end;
};

/*
 * Compare two directory entry names using an already-matched prefix.
 * (Linux equivalent: erofs_dirnamecmp in Linux's namei.c)
 *
 * qn: search key (not necessarily null-terminated).
 * qd: on-disk name range (may not be null-terminated).
 * matched: in/out count of prefix characters already known to match.
 *
 * Returns 0 if equal, 1 if qn > qd, -1 if qn < qd.
 */
static int
erofs_dirnamecmp(const struct erofs_qstr *qn, const struct erofs_qstr *qd,
    unsigned int *matched)
{
	size_t dname_span, qname_span;
	unsigned int i;

	qname_span = qn->end - qn->name;
	dname_span = qd->end - qd->name;
	i = MIN(*matched, qname_span);
	i = MIN(i, dname_span);
	while (i < qname_span && i < dname_span && qd->name[i] != '\0') {
		if (qn->name[i] != qd->name[i]) {
			*matched = i;
			return (qn->name[i] > qd->name[i] ? 1 : -1);
		}
		++i;
	}
	*matched = i;
	if (i == qname_span)
		return (i == dname_span || qd->name[i] == '\0' ? 0 : -1);
	return (1);
}

static int
erofs_dirent_qstr(const char *data, uint32_t datasize, uint32_t index,
    uint32_t ndirents, struct erofs_qstr *name)
{
	const struct erofs_dirent *de;
	uint32_t endoff, nameoff;
	size_t namelen;
	int error;

	de = (const struct erofs_dirent *)data;
	nameoff = le16toh(de[index].nameoff);
	endoff = index + 1 < ndirents ?
	    le16toh(de[index + 1].nameoff) : datasize;
	error = erofs_dirent_namelen(data, nameoff, endoff,
	    index + 1 == ndirents, &namelen);
	if (error != 0)
		return (error);
	name->name = (const unsigned char *)data + nameoff;
	name->end = name->name + namelen;
	return (0);
}

static int
erofs_read_dirblock(struct erofs_sb_info *sbi, struct erofs_inode *dir,
    uint64_t block, char **datap, uint32_t *datasizep, uint32_t *ndirentsp)
{
	erofs_off_t block_off;
	uint32_t datasize;
	char *data;
	int error;

	*datap = NULL;
	if (__builtin_mul_overflow(block, (uint64_t)sbi->block_size,
	    &block_off) || block_off >= dir->size)
		return (EINTEGRITY);
	datasize = MIN((uint64_t)sbi->block_size, dir->size - block_off);
	error = erofs_read_data(sbi, dir, block_off, datasize, (void **)&data);
	if (error != 0)
		return (error);
	error = erofs_validate_dirblock(data, sbi->block_size, datasize,
	    ndirentsp);
	if (error != 0) {
		erofs_brelse(data);
		return (error);
	}
	*datap = data;
	*datasizep = datasize;
	return (0);
}

static int
erofs_dirblock_order(const char *left, uint32_t leftsize,
    uint32_t leftents, const char *right, uint32_t rightsize,
    uint32_t rightents)
{
	struct erofs_qstr leftname, rightname;
	unsigned int matched;
	int error;

	error = erofs_dirent_qstr(left, leftsize, leftents - 1, leftents,
	    &leftname);
	if (error != 0)
		return (error);
	error = erofs_dirent_qstr(right, rightsize, 0, rightents, &rightname);
	if (error != 0)
		return (error);
	matched = 0;
	if (erofs_dirnamecmp(&leftname, &rightname, &matched) >= 0)
		return (EINTEGRITY);
	return (0);
}

static int
erofs_validate_dirblock_neighbors(struct erofs_sb_info *sbi,
    struct erofs_inode *dir, uint64_t block, const char *data,
    uint32_t datasize, uint32_t ndirents)
{
	uint64_t lastblock;
	uint32_t neighborsize, neighborents;
	char *neighbor;
	int error;

	lastblock = (dir->size - 1) / sbi->block_size;
	if (block > 0) {
		error = erofs_read_dirblock(sbi, dir, block - 1, &neighbor,
		    &neighborsize, &neighborents);
		if (error != 0)
			return (error);
		error = erofs_dirblock_order(neighbor, neighborsize,
		    neighborents, data, datasize, ndirents);
		erofs_brelse(neighbor);
		if (error != 0)
			return (error);
	}
	if (block < lastblock) {
		error = erofs_read_dirblock(sbi, dir, block + 1, &neighbor,
		    &neighborsize, &neighborents);
		if (error != 0)
			return (error);
		error = erofs_dirblock_order(data, datasize, ndirents,
		    neighbor, neighborsize, neighborents);
		erofs_brelse(neighbor);
		if (error != 0)
			return (error);
	}
	return (0);
}

/*
 * Binary search within a directory block for the target name.
 *
 * Returns a pointer to the matching dirent, or NULL on miss.
 */
static struct erofs_dirent *
find_target_dirent(const struct erofs_qstr *name, char *data,
    uint32_t datasize, uint32_t ndirents)
{
	uint32_t head, back;
	unsigned int startprfx, endprfx;
	struct erofs_dirent *const de = (struct erofs_dirent *)data;

	/* The 1st dirent has already been evaluated by the caller. */
	head = 1;
	back = ndirents - 1;
	startprfx = endprfx = 0;

	while (head <= back) {
		const uint32_t mid = head + (back - head) / 2;
		const uint32_t nameoff = le16toh(de[mid].nameoff);
		unsigned int matched = MIN(startprfx, endprfx);
		struct erofs_qstr dname = {
			.name = (const unsigned char *)data + nameoff,
		};

		if (mid >= ndirents - 1)
			dname.end = (const unsigned char *)data + datasize;
		else
			dname.end = (const unsigned char *)data +
			    le16toh(de[mid + 1].nameoff);

		/* String comparison without already matched prefix */
		int ret = erofs_dirnamecmp(name, &dname, &matched);

		if (ret == 0)
			return (de + mid);
		else if (ret > 0) {
			head = mid + 1;
			startprfx = matched;
		} else {
			back = mid - 1;
			endprfx = matched;
		}
	}

	return (NULL);
}

/*
 * Find the directory block most likely to contain the target name.
 *
 * Uses two-level binary search: first across blocks, then within the
 * candidate block via find_target_dirent().
 *
 * Returns the block buffer on success (caller must erofs_brelse),
 * or NULL on error.  *_ndirents is set to the number of dirents in
 * the returned block (0 means the first entry is the match).
 * On error, *errorp is set to a positive errno.
 */
static char *
erofs_find_target_block(struct erofs_sb_info *sbi, struct erofs_inode *dir,
    const struct erofs_qstr *name, uint32_t *_ndirents, uint32_t *_datasize,
    int *errorp)
{
	uint32_t bsz = sbi->block_size;
	uint64_t head, back;
	unsigned int startprfx = 0, endprfx = 0;
	char *candidate = NULL;
	int error;

	*errorp = 0;
	*_ndirents = 0;
	*_datasize = 0;

	if (dir->size == 0)
		return (NULL);

	head = 0;
	back = (dir->size - 1) / bsz;

	while (head <= back) {
		const uint64_t mid = head + (back - head) / 2;
		uint32_t maxsize;
		const struct erofs_dirent *de;
		char *blk;
		int diff;
		uint32_t ndirents;
		uint32_t nameoff;
		unsigned int matched;
		struct erofs_qstr dname;

		error = erofs_read_dirblock(sbi, dir, mid, &blk, &maxsize,
		    &ndirents);
		if (error != 0) {
			*errorp = error;
			goto out;
		}
		error = erofs_validate_dirblock_neighbors(sbi, dir, mid, blk,
		    maxsize, ndirents);
		if (error != 0) {
			erofs_brelse(blk);
			*errorp = error;
			goto out;
		}
		de = (const struct erofs_dirent *)blk;
		nameoff = le16toh(de[0].nameoff);

		matched = MIN(startprfx, endprfx);
		dname.name = (const unsigned char *)blk + nameoff;
		if (ndirents == 1)
			dname.end = (const unsigned char *)blk + maxsize;
		else
			dname.end = (const unsigned char *)blk +
			    le16toh(de[1].nameoff);

		/* String comparison without already matched prefix */
		diff = erofs_dirnamecmp(name, &dname, &matched);

		if (diff < 0) {
			erofs_brelse(blk);
			if (mid == 0)
				break;
			back = mid - 1;
			endprfx = matched;
			continue;
		}

		/* diff >= 0: this block is a candidate. */
		if (candidate != NULL)
			erofs_brelse(candidate);
		candidate = blk;
		if (diff == 0) {
			*_ndirents = 0;
			*_datasize = maxsize;
			return (candidate);
		}
		head = mid + 1;
		startprfx = matched;
		*_ndirents = ndirents;
		*_datasize = maxsize;
	}
	return (candidate);
out:
	if (candidate != NULL)
		erofs_brelse(candidate);
	return (NULL);
}

/*
 * Look up a name in a directory and return its nid and d_type.
 * (Linux equivalent: erofs_namei in Linux's namei.c)
 */
static int
erofs_namei(struct erofs_sb_info *sbi, struct erofs_inode *dir,
    const struct erofs_qstr *name, erofs_nid_t *nid, uint8_t *d_type)
{
	int error;
	uint32_t ndirents;
	uint32_t datasize;
	char *blk;
	struct erofs_dirent *de;

	if (dir->size == 0)
		return (ENOENT);

	blk = erofs_find_target_block(sbi, dir, name, &ndirents,
	    &datasize, &error);
	if (blk == NULL)
		return (error != 0 ? error : ENOENT);

	de = (struct erofs_dirent *)blk;
	if (ndirents > 0)
		de = find_target_dirent(name, blk, datasize,
		    ndirents);

	if (de != NULL) {
		erofs_nid_t found_nid;

		found_nid = le64toh(de->nid);
		if (!erofs_nid_is_valid(sbi, found_nid)) {
			error = EINTEGRITY;
		} else {
			*nid = found_nid;
			*d_type = de->file_type;
		}
	}
	erofs_brelse(blk);
	if (error != 0)
		return (error);
	return (de != NULL ? 0 : ENOENT);
}

/*
 * Directory name lookup (VOP_CACHEDLOOKUP entry point).
 *
 * FreeBSD-side API requirements:
 * - "." must be returned under the caller's requested lock mode;
 * - ".." must go through vn_vget_ino() to avoid holding a child lock while
 *   acquiring the parent directory lock in reverse;
 * - Both hit and miss must correctly update the namecache.
 */
int
erofs_lookup(struct vop_cachedlookup_args *ap)
{
	struct erofs_qstr qname;
	struct vnode *dvp, *vp;
	struct erofs_inode *dir;
	struct erofs_sb_info *sbi;
	struct componentname *cnp;
	erofs_nid_t nid;
	uint8_t dtype;
	int error, ltype;

	dvp = ap->a_dvp;
	cnp = ap->a_cnp;
	*ap->a_vpp = NULL;
	if ((cnp->cn_flags & ISLASTCN) != 0 &&
	    (cnp->cn_nameiop == DELETE || cnp->cn_nameiop == RENAME))
		return (EROFS);
	if (cnp->cn_namelen < 0)
		return (EINVAL);
	if (cnp->cn_namelen > EROFS_NAME_LEN)
		return (ENAMETOOLONG);
	if (cnp->cn_namelen == 1 && cnp->cn_nameptr[0] == '.') {
		vref(dvp);
		ltype = cnp->cn_lkflags & LK_TYPE_MASK;
		if (ltype != VOP_ISLOCKED(dvp)) {
			if (ltype == LK_EXCLUSIVE)
				vn_lock(dvp, LK_UPGRADE | LK_RETRY);
			else if (ltype == LK_SHARED)
				vn_lock(dvp, LK_DOWNGRADE | LK_RETRY);
		}
		*ap->a_vpp = dvp;
		return (0);
	}

	dir = VTOE(dvp);
	sbi = MTOE(dvp->v_mount);
	qname.name = (const unsigned char *)cnp->cn_nameptr;
	qname.end = qname.name + cnp->cn_namelen;
	error = erofs_namei(sbi, dir, &qname, &nid, &dtype);
	if (error != 0) {
		if (error == ENOENT && (cnp->cn_flags & MAKEENTRY) != 0)
			cache_enter(dvp, NULL, cnp);
		if (error == ENOENT && (cnp->cn_flags & ISLASTCN) != 0 &&
		    (cnp->cn_nameiop == CREATE || cnp->cn_nameiop == RENAME))
			return (EROFS);
		return (error);
	}
	if ((cnp->cn_flags & ISDOTDOT) == 0 && nid == dir->nid)
		return (EINTEGRITY);

	if ((cnp->cn_flags & ISDOTDOT) != 0)
		error = vn_vget_ino(dvp, nid, cnp->cn_lkflags, &vp);
	else
		error = erofs_vget(dvp->v_mount, nid, cnp->cn_lkflags, &vp);
	if (error != 0)
		return (error);
	if ((cnp->cn_flags & ISDOTDOT) == 0 &&
	    !erofs_dirent_type_matches(dtype, VTOE(vp)->vtype)) {
		vput(vp);
		return (EINTEGRITY);
	}
	*ap->a_vpp = vp;
	if ((cnp->cn_flags & MAKEENTRY) != 0)
		cache_enter(dvp, vp, cnp);
	return (0);
}