/*
 * Copyright (c) 2015-2020,2022 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#ifndef __OBJSTORE_DIR_H
#define __OBJSTORE_DIR_H

#include "objstore_impl.h"

/*
 * A directory is a file with a special format and a NATTR_DIR mode.  The
 * contents of the "file" are as follows.
 *
 * The contents are divided into blocks of DIR_BLOCK_SIZE bytes.  Therefore,
 * the size of this file is *always* a multiple of this length.
 *
 * Each block is self contained.  It contains a header (struct
 * obj_dir_header) and zero or more directory entries.  Each directory entry
 * is made up of 3 parts: the fixed sized entry (struct ndirent_phys), a
 * name string (a uint8_t array without the trailing nul), and a CBOR
 * sequence of one or more targets.
 *
 * The fixed sized entries are packed into an array that begins immediately
 * after the block header.  This makes it easy to index into.
 *
 * There are no requirements about the placement of names and targets except
 * that they must begin after the fixed sized entries.  (But not necessarily
 * immediately after.)  Therefore, all the names and targets can be grouped,
 * interleaved, with arbitrary padding between them.
 *
 * Visually, each block looks like:
 *
 *   |<---------------- DIR_BLOCK_SIZE --------------->|
 *   |                                                 |
 *   +--------+----------------+-----------------+-----+
 *   | header | ndirent_phys[] | names & targets | pad |
 *   +--------+----------------+-----------------+-----+
 *
 * Each struct ndirent_phys refers to one or more targets.  The targets are
 * packed into a CBOR sequence with each entry in the sequence being an
 * definite length array consisting of:
 *
 *  - dirent type
 *  - dirent type specific target info
 *    - grafts:
 *      - uuid
 *    - other:
 *      - oid host
 *      - oid uniq
 *  - flags (see DIRENT_TGT_FLAG_*)
 *
 * Note: Because grafts and other dirent types have a different number of
 * values stored, the target CBOR array will have a different number of
 * elements depending on the dirent type.  Specifically, a graft will have 3
 * elements while other types will have 4.
 */

#define OBJ_DIR_MAGIC	0x4e4449524f424a30ull	/* "NDIROBJ0" */

#define DIR_BLOCK_SIZE	4096

struct obj_dir_header {
	uint64_t magic;		/* OBJ_DIR_MAGIC */
	uint16_t ndirents;	/* number of dirents in this block */
	uint8_t _pad[22];
} __attribute__((packed,aligned(8)));

#define MAX_NAME_LEN	UINT8_MAX
#define NDIRENT_FLAG_CONFLICTS	0x8000 /* >1 non-deleted target */
#define NDIRENT_FLAG_ALL_DELS	0x4000 /* 0 non-deleted targets */
#define NDIRENT_NTGTS_MASK	0x3fff
struct ndirent_phys {
	uint16_t tgtoff; /* blk offset with target array */
	uint16_t ntgts_and_flags;  /* number of targets; flags in the MSBs */
	uint16_t nameoff;/* blk offset with name */
	uint8_t namelen; /* name length */
} __attribute__((packed,aligned(1)));

STATIC_ASSERT(sizeof(struct obj_dir_header) == 32);
STATIC_ASSERT(sizeof(struct ndirent_phys) == 7);

/*
 * unpacked dirent for easy processing
 *
 * Note: This struct resembles what's stored on disk.  It is not to be
 * confused with struct ndirent, which represents a higher level view - one
 * which combines a dirent with one of its targets.
 */
struct ndirent_mem {
	uint16_t tgtoff; /* blk offset with target array */
	uint16_t ntgts;  /* number of targets in this dirent */
	uint16_t nameoff;/* blk offset with name */
	uint8_t namelen; /* name length */
	bool conflicts; /* more than one non-deleted target */
	bool all_deleted; /* all targets are deleted */
};

/*
 * packed dirent tgt uses a CBOR array
 *
 * Best (impossible) case, each will consist of:
 *  - the array type byte (1 byte)
 *  - the dirent type uint (1 bytes since types <= 23)
 *  - target oid (graft uuid is 1+16)
 *    - host uint (1 bytes)
 *    - uniq uint (1 bytes)
 *  - flags (1 bytes)
 *
 * Worst case, each will consist of:
 *  - the array type byte (1 byte)
 *  - the dirent type uint (1 bytes since types <= 23)
 *  - target oid (graft uuid is only 1+16)
 *    - host uint (1+8 bytes)
 *    - uniq uint (1+8 bytes)
 *  - flags (1+8 bytes)
 */
#define PACKED_DIRENT_TGT_MIN_LEN	(1 + 1 + 1 + 1 + 1)
#define PACKED_DIRENT_TGT_MAX_LEN	(1 + 1 + (1 + 8) + (1 + 8) + (1 + 8))

/* dirent target flags */
#define DIRENT_TGT_FLAG_DELETED		0x0001 /* target removed by user */
#define DIRENT_TGT_ALL_FLAGS \
	(DIRENT_TGT_FLAG_DELETED)

/* unpacked dirent tgt for easy processing */
struct ndirent_tgt {
	uint8_t type;

	bool deleted;

	union {
		struct xuuid graft;
		struct {
			uint64_t host;
			uint64_t uniq;
		};
	};
};

/*
 * an easier to work with representation of a directory block
 *
 * To avoid unnecessary memory allocations, it includes more than enough
 * inline space for the fixed sized entries, their names, as well as their
 * targets.  (Technically, it has enough space for the worst possible case
 * for each - in other words, it is a bit wasteful.)
 */
#define DIRBLOCK_USABLE_SPACE	(DIR_BLOCK_SIZE - sizeof(struct obj_dir_header))

#define DIRBLOCK_MIN_NAME_SIZE	1 /* 1 byte min */
#define DIRBLOCK_MIN_ENTRY_SIZE	\
	(sizeof(struct ndirent_phys) + PACKED_DIRENT_TGT_MIN_LEN + \
	 DIRBLOCK_MIN_NAME_SIZE)

/* max number of fixed sized entries in a block */
#define DIRBLOCK_MAX_DIRENT_COUNT \
		(DIRBLOCK_USABLE_SPACE / DIRBLOCK_MIN_ENTRY_SIZE)
/* max number of bytes used by names in a block */
#define DIRBLOCK_MAX_NAME_SIZE \
		(DIRBLOCK_USABLE_SPACE - sizeof(struct ndirent_phys) - \
		 PACKED_DIRENT_TGT_MIN_LEN)
/* max number of targets in a block */
#define DIRBLOCK_MAX_TGT_COUNT \
		((DIRBLOCK_USABLE_SPACE - sizeof(struct ndirent_phys) - \
		  DIRBLOCK_MIN_NAME_SIZE) / PACKED_DIRENT_TGT_MIN_LEN)

/* make sure we have enough bits to keep track of all targets */
STATIC_ASSERT(NDIRENT_NTGTS_MASK >= DIRBLOCK_MAX_TGT_COUNT);

struct dirblock {
	size_t used_bytes; /* total bytes used in this block */
	size_t name_bytes; /* bytes used in this block for names */
	uint16_t ndirents; /* total number of dirents */
	uint16_t ntgts; /* total number of targets */

	struct {
		struct ndirent_mem dirent;

		/*
		 * instead of using tgtoff and nameoff in the above dirent,
		 * we use real pointers for convenience
		 */
		const char *name;
		struct ndirent_tgt *tgts;
	} entries[DIRBLOCK_MAX_DIRENT_COUNT];

	/* all the names concat'd, no trailing nuls */
	char names[DIRBLOCK_MAX_NAME_SIZE];

	/* all the targets concated */
	struct ndirent_tgt tgts[DIRBLOCK_MAX_TGT_COUNT];
};

extern void dirblock_init(struct dirblock *block);
extern int dirblock_parse(struct dirblock *block, uint8_t *raw, uint16_t ndirents);
extern int dirblock_serialize(struct dirblock *block, struct buffer *buf);
extern int dirblock_add_dirent(struct dirblock *block, const char *name,
			       const struct ndirent_tgt *tgt);
extern int dirblock_add_dirent_target(struct dirblock *block, const char *name,
				      const struct ndirent_tgt *tgt);

extern int dir_add_dirent(struct txn *txn, struct objver *dirver,
			  const char *name, uint16_t mode,
			  const struct noid *child);
extern int dir_update_dirent(struct txn *txn, struct objver *dirver,
			     uint8_t *raw, uint64_t diroff,
			     uint16_t ndirents, const char *name,
			     uint16_t mode, const struct noid *child);
extern int dir_lookup_entry(struct objver *dirver, const char *name,
			    uint8_t *raw, struct ndirent_mem *ent,
			    uint64_t *_off, uint16_t *_ndirents);

extern void dirent_cpu2be(struct ndirent_phys *phys, const struct ndirent_mem *mem);
extern void dirent_be2cpu(struct ndirent_mem *mem, const struct ndirent_phys *phys);

extern int pack_dirent_tgt(struct buffer *buf, const struct ndirent_tgt *tgt);
extern int unpack_dirent_tgt(struct buffer *buf, struct ndirent_tgt *tgt);

#endif