#include <sys/param.h>
#include <sys/systm.h>
#include <sys/vnode.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/proc.h>
#include <sys/queue.h>
#include "hfs.h"
#include "hfs_cnode.h"
extern lck_attr_t * hfs_lock_attr;
extern lck_grp_t * hfs_mutex_group;
extern lck_grp_t * hfs_rwlock_group;
lck_grp_t * chash_lck_grp;
lck_grp_attr_t * chash_lck_grp_attr;
lck_attr_t * chash_lck_attr;
static cnode_t *hfs_cnode_alloc(hfsmount_t *hfsmp, bool *unlocked);
#define CNODEHASH(hfsmp, inum) (&hfsmp->hfs_cnodehashtbl[(inum) & hfsmp->hfs_cnodehash])
static void hfs_cnode_zone_init(hfsmount_t *hfsmp);
static void hfs_cnode_zone_free(hfsmount_t *hfsmp);
void
hfs_chashinit()
{
chash_lck_grp_attr= lck_grp_attr_alloc_init();
chash_lck_grp = lck_grp_alloc_init("cnode_hash", chash_lck_grp_attr);
chash_lck_attr = lck_attr_alloc_init();
}
static void hfs_chash_lock(struct hfsmount *hfsmp)
{
lck_mtx_lock(&hfsmp->hfs_chash_mutex);
}
static void hfs_chash_lock_spin(struct hfsmount *hfsmp)
{
lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
}
static void hfs_chash_lock_convert(struct hfsmount *hfsmp)
{
lck_mtx_convert_spin(&hfsmp->hfs_chash_mutex);
}
static void hfs_chash_unlock(struct hfsmount *hfsmp)
{
lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
}
void
hfs_chashinit_finish(struct hfsmount *hfsmp)
{
lck_mtx_init(&hfsmp->hfs_chash_mutex, chash_lck_grp, chash_lck_attr);
hfsmp->hfs_cnodehashtbl = hashinit(desiredvnodes / 4, M_TEMP, &hfsmp->hfs_cnodehash);
hfs_cnode_zone_init(hfsmp);
}
void
hfs_delete_chash(struct hfsmount *hfsmp)
{
lck_mtx_destroy(&hfsmp->hfs_chash_mutex, chash_lck_grp);
FREE(hfsmp->hfs_cnodehashtbl, M_TEMP);
hfs_cnode_zone_free(hfsmp);
}
struct vnode *
hfs_chash_getvnode(struct hfsmount *hfsmp, ino_t inum, int wantrsrc, int skiplock, int allow_deleted)
{
struct cnode *cp;
struct vnode *vp;
int error;
u_int32_t vid;
loop:
hfs_chash_lock_spin(hfsmp);
for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
if (cp->c_fileid != inum)
continue;
if (ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
SET(cp->c_hflag, H_WAITING);
(void) msleep(cp, &hfsmp->hfs_chash_mutex, PDROP | PINOD,
"hfs_chash_getvnode", 0);
goto loop;
}
vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
if (vp == NULLVP)
goto exit;
vid = vnode_vid(vp);
hfs_chash_unlock(hfsmp);
if ((error = vnode_getwithvid(vp, vid))) {
return (NULL);
}
if (!skiplock && hfs_lock(cp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT) != 0) {
vnode_put(vp);
return (NULL);
}
if (!allow_deleted) {
if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
if (!skiplock) {
hfs_unlock(cp);
}
vnode_put(vp);
return (NULL);
}
}
return (vp);
}
exit:
hfs_chash_unlock(hfsmp);
return (NULL);
}
int
hfs_chash_snoop(struct hfsmount *hfsmp, ino_t inum, int existence_only,
int (*callout)(const cnode_t *cp, void *), void * arg)
{
struct cnode *cp;
int result = ENOENT;
hfs_chash_lock(hfsmp);
for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
if (cp->c_fileid != inum)
continue;
if (existence_only) {
result = 0;
break;
}
if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
result = EACCES;
break;
}
if (!ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
result = callout(cp, arg);
}
break;
}
hfs_chash_unlock(hfsmp);
return (result);
}
struct cnode *
hfs_chash_getcnode(struct hfsmount *hfsmp, ino_t inum, struct vnode **vpp,
int wantrsrc, int skiplock, int *out_flags, int *hflags)
{
struct cnode *cp;
struct cnode *ncp = NULL;
vnode_t vp;
u_int32_t vid;
loop:
hfs_chash_lock_spin(hfsmp);
loop_with_lock:
for (cp = CNODEHASH(hfsmp, inum)->lh_first; cp; cp = cp->c_hash.le_next) {
if (cp->c_fileid != inum)
continue;
if (ISSET(cp->c_hflag, H_ALLOC | H_ATTACH | H_TRANSIT)) {
SET(cp->c_hflag, H_WAITING);
(void) msleep(cp, &hfsmp->hfs_chash_mutex, PINOD,
"hfs_chash_getcnode", 0);
goto loop_with_lock;
}
vp = wantrsrc ? cp->c_rsrc_vp : cp->c_vp;
if (vp == NULL) {
SET(cp->c_hflag, H_ATTACH);
*hflags |= H_ATTACH;
hfs_chash_unlock(hfsmp);
} else {
vid = vnode_vid(vp);
hfs_chash_unlock(hfsmp);
if (vnode_getwithvid(vp, vid))
goto loop;
}
if (ncp) {
hfs_cnode_free(hfsmp, ncp);
ncp = NULL;
}
if (!skiplock) {
hfs_lock(cp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_ALLOW_NOEXISTS);
}
if ((cp->c_flag & (C_NOEXISTS | C_DELETED)) && !wantrsrc) {
int renamed = 0;
if (cp->c_flag & C_RENAMED) {
renamed = 1;
}
if (!skiplock)
hfs_unlock(cp);
if (vp != NULLVP) {
vnode_put(vp);
} else {
hfs_chash_lock_spin(hfsmp);
CLR(cp->c_hflag, H_ATTACH);
*hflags &= ~H_ATTACH;
if (ISSET(cp->c_hflag, H_WAITING)) {
CLR(cp->c_hflag, H_WAITING);
wakeup((caddr_t)cp);
}
hfs_chash_unlock(hfsmp);
}
vp = NULL;
cp = NULL;
if (renamed) {
*out_flags = GNV_CHASH_RENAMED;
}
}
*vpp = vp;
return (cp);
}
if (skiplock && !wantrsrc)
panic("%s - should never get here when skiplock is set \n", __FUNCTION__);
if (ncp == NULL) {
bool unlocked;
ncp = hfs_cnode_alloc(hfsmp, &unlocked);
if (unlocked)
goto loop_with_lock;
}
hfs_chash_lock_convert(hfsmp);
#if HFS_MALLOC_DEBUG
bzero(ncp, __builtin_offsetof(struct cnode, magic));
#else
bzero(ncp, sizeof(*ncp));
#endif
SET(ncp->c_hflag, H_ALLOC);
*hflags |= H_ALLOC;
ncp->c_fileid = inum;
TAILQ_INIT(&ncp->c_hintlist);
TAILQ_INIT(&ncp->c_originlist);
lck_rw_init(&ncp->c_rwlock, hfs_rwlock_group, hfs_lock_attr);
if (!skiplock)
(void) hfs_lock(ncp, HFS_EXCLUSIVE_LOCK, HFS_LOCK_DEFAULT);
LIST_INSERT_HEAD(CNODEHASH(hfsmp, inum), ncp, c_hash);
hfs_chash_unlock(hfsmp);
*vpp = NULL;
return (ncp);
}
void
hfs_chashwakeup(struct hfsmount *hfsmp, struct cnode *cp, int hflags)
{
hfs_chash_lock_spin(hfsmp);
CLR(cp->c_hflag, hflags);
if (ISSET(cp->c_hflag, H_WAITING)) {
CLR(cp->c_hflag, H_WAITING);
wakeup((caddr_t)cp);
}
hfs_chash_unlock(hfsmp);
}
void
hfs_chash_rehash(struct hfsmount *hfsmp, struct cnode *cp1, struct cnode *cp2)
{
hfs_chash_lock_spin(hfsmp);
LIST_REMOVE(cp1, c_hash);
LIST_REMOVE(cp2, c_hash);
LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp1->c_fileid), cp1, c_hash);
LIST_INSERT_HEAD(CNODEHASH(hfsmp, cp2->c_fileid), cp2, c_hash);
hfs_chash_unlock(hfsmp);
}
int
hfs_chashremove(struct hfsmount *hfsmp, struct cnode *cp)
{
hfs_chash_lock_spin(hfsmp);
if (ISSET(cp->c_hflag, H_ATTACH)) {
hfs_chash_unlock(hfsmp);
return (EBUSY);
}
if (cp->c_hash.le_next || cp->c_hash.le_prev) {
LIST_REMOVE(cp, c_hash);
cp->c_hash.le_next = NULL;
cp->c_hash.le_prev = NULL;
}
hfs_chash_unlock(hfsmp);
return (0);
}
void
hfs_chash_abort(struct hfsmount *hfsmp, struct cnode *cp)
{
hfs_chash_lock_spin(hfsmp);
LIST_REMOVE(cp, c_hash);
cp->c_hash.le_next = NULL;
cp->c_hash.le_prev = NULL;
CLR(cp->c_hflag, H_ATTACH | H_ALLOC);
if (ISSET(cp->c_hflag, H_WAITING)) {
CLR(cp->c_hflag, H_WAITING);
wakeup((caddr_t)cp);
}
hfs_chash_unlock(hfsmp);
}
void
hfs_chash_mark_in_transit(struct hfsmount *hfsmp, struct cnode *cp)
{
hfs_chash_lock_spin(hfsmp);
SET(cp->c_hflag, H_TRANSIT);
hfs_chash_unlock(hfsmp);
}
static
struct cnode *
hfs_chash_search_cnid(struct hfsmount *hfsmp, cnid_t cnid)
{
struct cnode *cp;
for (cp = CNODEHASH(hfsmp, cnid)->lh_first; cp; cp = cp->c_hash.le_next) {
if (cp->c_fileid == cnid) {
break;
}
}
if (cp && ISSET(cp->c_hflag, H_ALLOC | H_TRANSIT | H_ATTACH)) {
cp = NULL;
}
return cp;
}
int
hfs_chash_set_childlinkbit(struct hfsmount *hfsmp, cnid_t cnid)
{
int retval = -1;
struct cnode *cp;
hfs_chash_lock_spin(hfsmp);
cp = hfs_chash_search_cnid(hfsmp, cnid);
if (cp) {
if (cp->c_attr.ca_recflags & kHFSHasChildLinkMask) {
retval = 0;
} else {
cp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
retval = 1;
}
}
hfs_chash_unlock(hfsmp);
return retval;
}
enum {
CHUNK_HDR_MAGIC = 0x6b6e6863, CNODE_MAGIC = 0x65646f6e63736668, ELEMENT_ALIGNMENT = 8,
CHUNK_TAIL_LEN = 8,
};
typedef struct chunk_hdr
{
void *next_free;
uint32_t magic; uint16_t free_count;
uint16_t heap_ndx;
struct chunk_hdr **phdr;
} chunk_hdr_t;
static void hfs_cnode_zone_init(hfsmount_t *hfsmp)
{
struct cnode_zone *z = &hfsmp->z;
int elem_size = sizeof(cnode_t);
elem_size = roundup(elem_size, ELEMENT_ALIGNMENT);
z->elem_size = elem_size;
int npages, chunk_size, waste;
for (npages = 1;; ++npages) {
chunk_size = npages * page_size;
waste = (chunk_size - CHUNK_TAIL_LEN) % elem_size;
if (waste < chunk_size / 100)
break;
}
z->chunk_size = chunk_size;
z->alloc_count = (chunk_size - CHUNK_TAIL_LEN) / elem_size;
int t = 1, last_t = 0, r = z->elem_size, last_r = PAGE_SIZE;
while (r != 0) {
int q = last_r / r;
int next_r = last_r - q * r;
last_r = r;
r = next_r;
int next_t = last_t - q * t;
last_t = t;
t = next_t;
}
z->gcd = last_r;
z->y = last_t;
z->heap_max_count = 128 / sizeof(void *);
z->heap = hfs_malloc(z->heap_max_count * sizeof(void *));
#if DEBUG
printf("hfs: cnode size %d, chunk size %d, # per chunk %d, waste %d\n",
elem_size, chunk_size, z->alloc_count, waste);
#endif
}
static void hfs_cnode_zone_free(hfsmount_t *hfsmp)
{
struct cnode_zone *z = &hfsmp->z;
for (int i = 0; i < z->heap_count; ++i) {
#if DEBUG
hfs_assert(z->heap[i]->free_count == z->alloc_count);
#else
if (z->heap[i]->free_count != z->alloc_count) {
printf("hfs: cnodes leaked!\n");
continue;
}
#endif
void *chunk = (void *)((uintptr_t)z->heap[i]->phdr
- (z->chunk_size - CHUNK_TAIL_LEN));
hfs_free(chunk, z->chunk_size);
}
hfs_free(z->heap, z->heap_max_count * sizeof(void *));
}
static void *zel(struct cnode_zone *z, void *chunk, int i)
{
return chunk + i * z->elem_size;
}
static chunk_hdr_t **zphdr(struct cnode_zone *z, void *chunk)
{
return chunk + z->chunk_size - CHUNK_TAIL_LEN;
}
#if 0
static void hfs_check_heap(hfsmount_t *hfsmp, void *just_removed)
{
struct cnode_zone *z = &hfsmp->z;
for (int i = 0; i < z->heap_count; ++i) {
hfs_assert(z->heap[i]->magic == CHUNK_HDR_MAGIC);
hfs_assert(z->heap[i]->free_count > 0
&& z->heap[i]->free_count <= z->alloc_count);
hfs_assert(z->heap[i]->heap_ndx == i);
void *max_el = z->heap[i]->phdr;
void *min_el = (void *)((uintptr_t)z->heap[i]->phdr
+ CHUNK_TAIL_LEN - z->chunk_size);
int count = 1;
hfs_assert(z->heap[i] != just_removed);
void *el = z->heap[i]->next_free;
size_t bitmap_size = (z->alloc_count + 7) / 8;
uint8_t bitmap[bitmap_size];
bzero(bitmap, bitmap_size);
int ndx = (int)((void *)z->heap[i] - min_el) / z->elem_size;
bitmap[ndx / 8] |= 0x80 >> ndx % 8;
while (el) {
hfs_assert(el != just_removed);
hfs_assert(el >= min_el
&& el < max_el && (el - min_el) % z->elem_size == 0);
int n = (int)(el - min_el) / z->elem_size;
hfs_assert(!(bitmap[n / 8] & (0x80 >> n % 8)));
bitmap[n / 8] |= 0x80 >> n % 8;
el = *(void **)el;
++count;
}
hfs_assert(count == z->heap[i]->free_count);
if (i)
hfs_assert(z->heap[(i + 1) / 2 - 1]->free_count <= z->heap[i]->free_count);
}
}
#else
#define hfs_check_heap(a, b) (void)0
#endif
static void hfs_cnode_set_magic(cnode_t *cp, uint64_t v)
{
#if HFS_MALLOC_DEBUG
cp->magic = v;
#endif
}
static cnode_t *hfs_cnode_alloc(hfsmount_t *hfsmp, bool *unlocked)
{
hfs_check_heap(hfsmp, NULL);
*unlocked = false;
struct cnode_zone *z = &hfsmp->z;
void *el;
while (!z->heap_count) {
if (z->spare) {
chunk_hdr_t *chunk_hdr = z->spare;
z->spare = NULL;
void *last = NULL;
for (int i = z->alloc_count - 2; i > 0; --i) {
void *p = zel(z, chunk_hdr, i);
*(void **)p = last;
hfs_cnode_set_magic(p, 0);
last = p;
}
hfs_cnode_set_magic((void *)chunk_hdr, 0);
chunk_hdr->phdr = zphdr(z, chunk_hdr);
chunk_hdr->next_free = last;
chunk_hdr->free_count = z->alloc_count - 1;
chunk_hdr->heap_ndx = 0;
*zphdr(z, chunk_hdr) = chunk_hdr;
z->heap[0] = chunk_hdr;
z->heap_count = 1;
el = zel(z, chunk_hdr, z->alloc_count - 1);
hfs_cnode_set_magic(el, 0);
goto exit;
}
*unlocked = true;
if (z->allocating) {
z->waiting = true;
msleep(z, &hfsmp->hfs_chash_mutex, PINOD | PSPIN,
"hfs_cnode_alloc", NULL);
} else {
z->allocating = true;
lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
chunk_hdr_t *chunk_hdr = hfs_malloc(z->chunk_size);
chunk_hdr->magic = CHUNK_HDR_MAGIC;
hfs_assert(!((uintptr_t)chunk_hdr & PAGE_MASK));
lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
z->allocating = false;
if (z->waiting) {
wakeup(z);
z->waiting = false;
}
hfs_assert(!z->spare);
z->spare = chunk_hdr;
}
}
chunk_hdr_t *chunk_hdr = z->heap[0];
if (chunk_hdr->next_free) {
el = chunk_hdr->next_free;
chunk_hdr->next_free = *(void **)chunk_hdr->next_free;
--chunk_hdr->free_count;
goto exit;
}
el = chunk_hdr;
*chunk_hdr->phdr = NULL;
chunk_hdr->magic = ~CHUNK_HDR_MAGIC;
if (!--z->heap_count)
goto exit;
chunk_hdr_t *v = z->heap[z->heap_count];
int k = 1;
chunk_hdr_t **a = &z->heap[0] - 1;
int N = z->heap_count;
for (;;) {
int j = k * 2;
if (j > N)
break;
if (j < N && a[j]->free_count > a[j+1]->free_count)
++j;
if (v->free_count <= a[j]->free_count)
break;
a[k] = a[j];
a[k]->heap_ndx = k - 1;
k = j;
}
a[k] = v;
a[k]->heap_ndx = k - 1;
exit:
hfs_check_heap(hfsmp, el);
#if HFS_MALLOC_DEBUG
if (((cnode_t *)el)->magic == CNODE_MAGIC) {
#if __x86_64__
asm("int $3\n");
#elif __arm64__
asm("svc 0\n");
#else
asm("trap\n");
#endif
}
#endif // HFS_MALLOC_DEBUG
hfs_cnode_set_magic(el, CNODE_MAGIC);
return el;
}
void hfs_cnode_free(hfsmount_t *hfsmp, cnode_t *cp)
{
void *el = cp;
void *old_heap = NULL;
size_t old_heap_size = 0;
struct cnode_zone *z = &hfsmp->z;
int ndx_in_chunk = (z->y * (uintptr_t)el % PAGE_SIZE
/ z->gcd % (PAGE_SIZE / z->gcd));
void *free_chunk = NULL, *chunk = el - ndx_in_chunk * z->elem_size;
lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
#if HFS_MALLOC_DEBUG
hfs_assert(cp->magic == CNODE_MAGIC);
cp->magic = ~CNODE_MAGIC;
#endif
loop:
hfs_check_heap(hfsmp, NULL);
chunk_hdr_t *hdr = *zphdr(z, chunk);
int k, orig_k;
if (hdr) {
hfs_assert(hdr->magic == CHUNK_HDR_MAGIC);
*(void **)el = hdr->next_free;
hdr->next_free = el;
hfs_assert(hdr->next_free != hdr);
chunk_hdr_t *v;
orig_k = k = hdr->heap_ndx + 1;
chunk_hdr_t **a = &z->heap[0] - 1;
if (++hdr->free_count == z->alloc_count) {
if (z->heap_count == 1)
goto exit;
free_chunk = chunk;
--z->heap_count;
v = z->heap[z->heap_count];
if (k > 1 && a[k / 2]->free_count > v->free_count) {
do {
a[k] = a[k / 2];
a[k]->heap_ndx = k - 1;
k = k / 2;
} while (k > 1 && a[k / 2]->free_count > v->free_count);
a[k] = v;
a[k]->heap_ndx = k - 1;
goto exit;
}
} else
v = hdr;
int N = z->heap_count;
for (;;) {
int j = k * 2;
if (j > N)
break;
if (j < N && a[j]->free_count > a[j+1]->free_count)
++j;
if (v->free_count <= a[j]->free_count)
break;
a[k] = a[j];
a[k]->heap_ndx = k - 1;
k = j;
}
a[k] = v;
a[k]->heap_ndx = k - 1;
} else {
if (z->heap_count == z->heap_max_count) {
int new_max_count = z->heap_max_count * 2;
lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
if (old_heap)
hfs_free(old_heap, old_heap_size);
struct chunk_hdr **new_heap = hfs_malloc(new_max_count * sizeof(void *));
lck_mtx_lock_spin(&hfsmp->hfs_chash_mutex);
if (new_max_count > z->heap_max_count) {
memcpy(new_heap, z->heap, z->heap_count * sizeof(void *));
old_heap_size = z->heap_max_count * sizeof(void *);
z->heap_max_count = new_max_count;
old_heap = z->heap;
z->heap = new_heap;
} else {
old_heap = new_heap;
old_heap_size = new_max_count * sizeof(void *);
}
goto loop;
}
hdr = (chunk_hdr_t *)el;
*zphdr(z, chunk) = hdr;
hdr->free_count = 1;
hdr->next_free = NULL;
hdr->heap_ndx = 0;
hdr->phdr = zphdr(z, chunk);
hdr->magic = CHUNK_HDR_MAGIC;
chunk_hdr_t **a = &z->heap[0] - 1;
if (z->heap_count++) {
k = z->heap_count;
chunk_hdr_t *v = z->heap[0];
while (k > 3 && a[k / 2]->free_count > v->free_count) {
a[k] = a[k / 2];
a[k]->heap_ndx = k - 1;
k = k / 2;
}
a[k] = v;
a[k]->heap_ndx = k - 1;
}
z->heap[0] = hdr;
}
exit:
hfs_check_heap(hfsmp, NULL);
lck_mtx_unlock(&hfsmp->hfs_chash_mutex);
if (old_heap)
hfs_free(old_heap, old_heap_size);
if (free_chunk)
hfs_free(free_chunk, z->chunk_size);
}