FreeBSD ZFS
The Zettabyte File System
Data Structures | Defines | Typedefs | Enumerations | Functions

sys/zap_leaf.h File Reference

#include <sys/zap.h>
Include dependency graph for zap_leaf.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  zap_leaf_phys
struct  zap_leaf_phys::zap_leaf_header
union  zap_leaf_chunk
struct  zap_leaf_chunk::zap_leaf_entry
struct  zap_leaf_chunk::zap_leaf_array
struct  zap_leaf_chunk::zap_leaf_free
struct  zap_leaf
struct  zap_entry_handle

Defines

#define ZAP_LEAF_MAGIC   0x2AB1EAF
#define ZAP_LEAF_CHUNKSIZE   24
 chunk size = 24 bytes
#define ZAP_LEAF_NUMCHUNKS(l)
 The amount of space available for chunks is: block size (1<<l->l_bs) - hash entry size (2) * number of hash entries - header space (2*chunksize)
#define ZAP_LEAF_ARRAY_BYTES   (ZAP_LEAF_CHUNKSIZE - 3)
 The amount of space within the chunk available for the array is: chunk size - space for type (1) - space for next pointer (2)
#define ZAP_LEAF_ARRAY_NCHUNKS(bytes)   (((bytes)+ZAP_LEAF_ARRAY_BYTES-1)/ZAP_LEAF_ARRAY_BYTES)
#define ZAP_LEAF_LOW_WATER   (20)
 Low water mark: when there are only this many chunks free, start growing the ptrtbl.
#define ZAP_LEAF_HASH_SHIFT(l)   ((l)->l_bs - 5)
 The leaf hash table has block size / 2^5 (32) number of entries, which should be more than enough for the maximum number of entries, which is less than block size / CHUNKSIZE (24) / minimum number of chunks per entry (3).
#define ZAP_LEAF_HASH_NUMENTRIES(l)   (1 << ZAP_LEAF_HASH_SHIFT(l))
#define ZAP_LEAF_CHUNK(l, idx)
 The chunks start immediately after the hash table.
#define ZAP_LEAF_ENTRY(l, idx)   (&ZAP_LEAF_CHUNK(l, idx).l_entry)
#define ZLF_ENTRIES_CDSORTED   (1<<0)

Typedefs

typedef enum zap_chunk_type zap_chunk_type_t
typedef struct zap_leaf_phys zap_leaf_phys_t
typedef union zap_leaf_chunk zap_leaf_chunk_t
typedef struct zap_leaf zap_leaf_t
typedef struct zap_entry_handle zap_entry_handle_t

Enumerations

enum  zap_chunk_type { ZAP_CHUNK_FREE = 253, ZAP_CHUNK_ENTRY = 252, ZAP_CHUNK_ARRAY = 251, ZAP_CHUNK_TYPE_MAX = 250 }

Functions

int zap_leaf_lookup (zap_leaf_t *l, struct zap_name *zn, zap_entry_handle_t *zeh)
 Lookup a ZAP Leaf.
int zap_leaf_lookup_closest (zap_leaf_t *l, uint64_t hash, uint32_t cd, zap_entry_handle_t *zeh)
int zap_entry_read (const zap_entry_handle_t *zeh, uint8_t integer_size, uint64_t num_integers, void *buf)
 Read the first num_integers in the attribute.
int zap_entry_read_name (struct zap *zap, const zap_entry_handle_t *zeh, uint16_t buflen, char *buf)
int zap_entry_update (zap_entry_handle_t *zeh, uint8_t integer_size, uint64_t num_integers, const void *buf)
 Replace the value of an existing entry.
void zap_entry_remove (zap_entry_handle_t *zeh)
 Remove an entry.
int zap_entry_create (zap_leaf_t *l, struct zap_name *zn, uint32_t cd, uint8_t integer_size, uint64_t num_integers, const void *buf, zap_entry_handle_t *zeh)
 Create an entry.
boolean_t zap_entry_normalization_conflict (zap_entry_handle_t *zeh, struct zap_name *zn, const char *name, struct zap *zap)
 Determine if there is another entry with the same normalized form.
void zap_leaf_init (zap_leaf_t *l, boolean_t sort)
void zap_leaf_byteswap (zap_leaf_phys_t *buf, int len)
void zap_leaf_split (zap_leaf_t *l, zap_leaf_t *nl, boolean_t sort)
 Transfer the entries whose hash prefix ends in 1 to the new leaf.
void zap_leaf_stats (struct zap *zap, zap_leaf_t *l, struct zap_stats *zs)

Define Documentation

#define ZAP_LEAF_ARRAY_BYTES   (ZAP_LEAF_CHUNKSIZE - 3)

The amount of space within the chunk available for the array is: chunk size - space for type (1) - space for next pointer (2)

Definition at line 56 of file zap_leaf.h.

#define ZAP_LEAF_ARRAY_NCHUNKS (   bytes)    (((bytes)+ZAP_LEAF_ARRAY_BYTES-1)/ZAP_LEAF_ARRAY_BYTES)

Definition at line 58 of file zap_leaf.h.

#define ZAP_LEAF_CHUNK (   l,
  idx 
)
Value:
((zap_leaf_chunk_t *) \
        ((l)->l_phys->l_hash + ZAP_LEAF_HASH_NUMENTRIES(l)))[idx]

The chunks start immediately after the hash table.

The end of the hash table is at l_hash + HASH_NUMENTRIES, which we simply cast to a chunk_t.

Definition at line 84 of file zap_leaf.h.

#define ZAP_LEAF_CHUNKSIZE   24

chunk size = 24 bytes

Definition at line 41 of file zap_leaf.h.

#define ZAP_LEAF_ENTRY (   l,
  idx 
)    (&ZAP_LEAF_CHUNK(l, idx).l_entry)

Definition at line 87 of file zap_leaf.h.

#define ZAP_LEAF_HASH_NUMENTRIES (   l)    (1 << ZAP_LEAF_HASH_SHIFT(l))

Definition at line 77 of file zap_leaf.h.

#define ZAP_LEAF_HASH_SHIFT (   l)    ((l)->l_bs - 5)

The leaf hash table has block size / 2^5 (32) number of entries, which should be more than enough for the maximum number of entries, which is less than block size / CHUNKSIZE (24) / minimum number of chunks per entry (3).

Definition at line 76 of file zap_leaf.h.

#define ZAP_LEAF_LOW_WATER   (20)

Low water mark: when there are only this many chunks free, start growing the ptrtbl.

Ideally, this should be larger than a "reasonably-sized" entry. 20 chunks is more than enough for the largest directory entry (MAXNAMELEN (256) byte name, 8-byte value), while still being only around 3% for 16k blocks.

Definition at line 68 of file zap_leaf.h.

#define ZAP_LEAF_MAGIC   0x2AB1EAF

Definition at line 38 of file zap_leaf.h.

#define ZAP_LEAF_NUMCHUNKS (   l)
Value:
(((1<<(l)->l_bs) - 2*ZAP_LEAF_HASH_NUMENTRIES(l)) / \
        ZAP_LEAF_CHUNKSIZE - 2)

The amount of space available for chunks is: block size (1<<l->l_bs) - hash entry size (2) * number of hash entries - header space (2*chunksize)

Definition at line 48 of file zap_leaf.h.

#define ZLF_ENTRIES_CDSORTED   (1<<0)

Definition at line 96 of file zap_leaf.h.

Typedef Documentation

typedef enum zap_chunk_type zap_chunk_type_t
typedef struct zap_entry_handle zap_entry_handle_t
typedef union zap_leaf_chunk zap_leaf_chunk_t
typedef struct zap_leaf_phys zap_leaf_phys_t
Note:
If zap_leaf_phys_t is modified, zap_leaf_byteswap() must be modified.
typedef struct zap_leaf zap_leaf_t

Enumeration Type Documentation

enum zap_chunk_type
Enumerator:
ZAP_CHUNK_FREE 
ZAP_CHUNK_ENTRY 
ZAP_CHUNK_ARRAY 
ZAP_CHUNK_TYPE_MAX 

Definition at line 89 of file zap_leaf.h.

Function Documentation

int zap_entry_create ( zap_leaf_t *  l,
struct zap_name *  zn,
uint32_t  cd,
uint8_t  integer_size,
uint64_t  num_integers,
const void *  buf,
zap_entry_handle_t *  zeh 
)

Create an entry.

An equal entry must not exist, and this entry must belong in this leaf (according to its hash value). Fills in the entry handle on success.

Returns:
0 on success or an error code on failure

Definition at line 576 of file zap_leaf.c.

boolean_t zap_entry_normalization_conflict ( zap_entry_handle_t *  zeh,
zap_name_t *  zn,
const char *  name,
zap_t *  zap 
)

Determine if there is another entry with the same normalized form.

For performance purposes, either zn or name must be provided (the other can be NULL). Note, there usually won't be any hash conflicts, in which case we don't need the concatenated/normalized form of the name. But all callers have one of these on hand anyway, so might as well take advantage. A cleaner but slower interface would accept neither argument, and compute the normalized name as needed (using zap_name_alloc(zap_entry_read_name(zeh))).

Definition at line 677 of file zap_leaf.c.

int zap_entry_read ( const zap_entry_handle_t *  zeh,
uint8_t  integer_size,
uint64_t  num_integers,
void *  buf 
)

Read the first num_integers in the attribute.

Integer size conversion will be done without sign extension.

Return values:
0Success
EINVALinteger_size is too small
EOVERFLOWThere are more than num_integers in the attribute.

Definition at line 491 of file zap_leaf.c.

int zap_entry_read_name ( struct zap *  zap,
const zap_entry_handle_t *  zeh,
uint16_t  buflen,
char *  buf 
)

Definition at line 512 of file zap_leaf.c.

void zap_entry_remove ( zap_entry_handle_t *  zeh)

Remove an entry.

Definition at line 554 of file zap_leaf.c.

int zap_entry_update ( zap_entry_handle_t *  zeh,
uint8_t  integer_size,
uint64_t  num_integers,
const void *  buf 
)

Replace the value of an existing entry.

May fail if it runs out of space (ENOSPC).

Definition at line 532 of file zap_leaf.c.

void zap_leaf_byteswap ( zap_leaf_phys_t *  buf,
int  len 
)

Definition at line 104 of file zap_leaf.c.

void zap_leaf_init ( zap_leaf_t *  l,
boolean_t  sort 
)

Definition at line 156 of file zap_leaf.c.

int zap_leaf_lookup ( zap_leaf_t *  l,
struct zap_name *  zn,
zap_entry_handle_t *  zeh 
)

Lookup a ZAP Leaf.

The hash value must equal zap_hash(name).

Returns:
A handle to the named entry, or ENOENT if not found.

Definition at line 394 of file zap_leaf.c.

int zap_leaf_lookup_closest ( zap_leaf_t *  l,
uint64_t  hash,
uint32_t  cd,
zap_entry_handle_t *  zeh 
)
Returns:
A handle to the entry with this hash+cd, or the entry with the next closest hash+cd.

Definition at line 449 of file zap_leaf.c.

void zap_leaf_split ( zap_leaf_t *  l,
zap_leaf_t *  nl,
boolean_t  sort 
)

Transfer the entries whose hash prefix ends in 1 to the new leaf.

Definition at line 796 of file zap_leaf.c.

void zap_leaf_stats ( struct zap *  zap,
zap_leaf_t *  l,
struct zap_stats *  zs 
)

Definition at line 835 of file zap_leaf.c.

 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines
Generated on Sat Nov 17 2012 21:17:24 for FreeBSD ZFS by  doxygen 1.7.3