Lines Matching defs:dh
82 static int ulfsdirhash_hash(struct dirhash *dh, const char *name, int namelen);
83 static void ulfsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff,
85 static void ulfsdirhash_delslot(struct dirhash *dh, int slot);
86 static int ulfsdirhash_findslot(struct dirhash *dh, const char *name,
97 #define DIRHASH_LOCK(dh) mutex_enter(&(dh)->dh_lock)
98 #define DIRHASH_UNLOCK(dh) mutex_exit(&(dh)->dh_lock)
130 struct dirhash *dh;
172 memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
173 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
174 nblocks * sizeof(*dh->dh_blkfree);
192 dh = pool_cache_get(ulfsdirhash_cache, PR_NOWAIT);
193 if (dh == NULL) {
197 memset(dh, 0, sizeof(*dh));
198 mutex_init(&dh->dh_lock, MUTEX_DEFAULT, IPL_NONE);
199 DIRHASH_LOCK(dh);
200 dh->dh_hashsz = narrays * sizeof(dh->dh_hash[0]);
201 dh->dh_hash = kmem_zalloc(dh->dh_hashsz, KM_NOSLEEP);
202 dh->dh_blkfreesz = nblocks * sizeof(dh->dh_blkfree[0]);
203 dh->dh_blkfree = kmem_zalloc(dh->dh_blkfreesz, KM_NOSLEEP);
204 if (dh->dh_hash == NULL || dh->dh_blkfree == NULL)
207 if ((dh->dh_hash[i] = DIRHASH_BLKALLOC()) == NULL)
210 dh->dh_hash[i][j] = DIRHASH_EMPTY;
214 dh->dh_narrays = narrays;
215 dh->dh_hlen = nslots;
216 dh->dh_nblk = nblocks;
217 dh->dh_dirblks = dirblocks;
219 dh->dh_blkfree[i] = dirblksiz / DIRALIGN;
221 dh->dh_firstfree[i] = -1;
222 dh->dh_firstfree[DH_NFSTATS] = 0;
223 dh->dh_seqopt = 0;
224 dh->dh_seqoff = 0;
225 dh->dh_score = DH_SCOREINIT;
226 ip->i_dirhash = dh;
251 slot = ulfsdirhash_hash(dh, lfs_dir_nameptr(fs, ep),
253 while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
254 slot = WRAPINCR(slot, dh->dh_hlen);
255 dh->dh_hused++;
256 DH_ENTRY(dh, slot) = pos;
257 ulfsdirhash_adjfree(dh, pos, -LFS_DIRSIZ(fs, ep),
266 TAILQ_INSERT_TAIL(&ulfsdirhash_list, dh, dh_list);
267 dh->dh_onlist = 1;
268 DIRHASH_UNLOCK(dh);
274 DIRHASH_UNLOCK(dh);
275 if (dh->dh_hash != NULL) {
277 if (dh->dh_hash[i] != NULL)
278 DIRHASH_BLKFREE(dh->dh_hash[i]);
279 kmem_free(dh->dh_hash, dh->dh_hashsz);
281 if (dh->dh_blkfree != NULL)
282 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
283 mutex_destroy(&dh->dh_lock);
284 pool_cache_put(ulfsdirhash_cache, dh);
295 struct dirhash *dh;
298 if ((dh = ip->i_dirhash) == NULL)
303 if (dh->dh_onlist) {
305 if (dh->dh_onlist)
306 TAILQ_REMOVE(&ulfsdirhash_list, dh, dh_list);
310 /* The dirhash pointed to by 'dh' is exclusively ours now. */
311 mem = sizeof(*dh);
312 if (dh->dh_hash != NULL) {
313 for (i = 0; i < dh->dh_narrays; i++)
314 DIRHASH_BLKFREE(dh->dh_hash[i]);
315 kmem_free(dh->dh_hash, dh->dh_hashsz);
316 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
317 mem += dh->dh_hashsz;
318 mem += dh->dh_narrays * DH_NBLKOFF * sizeof(**dh->dh_hash);
319 mem += dh->dh_nblk * sizeof(*dh->dh_blkfree);
321 mutex_destroy(&dh->dh_lock);
322 pool_cache_put(ulfsdirhash_cache, dh);
343 struct dirhash *dh, *dh_next;
351 if ((dh = ip->i_dirhash) == NULL)
362 if (TAILQ_NEXT(dh, dh_list) != NULL) {
364 DIRHASH_LOCK(dh);
371 if (dh->dh_hash != NULL &&
372 (dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
373 dh->dh_score >= dh_next->dh_score) {
374 KASSERT(dh->dh_onlist);
375 TAILQ_REMOVE(&ulfsdirhash_list, dh, dh_list);
376 TAILQ_INSERT_AFTER(&ulfsdirhash_list, dh_next, dh,
382 DIRHASH_LOCK(dh);
384 if (dh->dh_hash == NULL) {
385 DIRHASH_UNLOCK(dh);
391 if (dh->dh_score < DH_SCOREMAX)
392 dh->dh_score++;
399 slot = ulfsdirhash_hash(dh, name, namelen);
401 if (dh->dh_seqopt) {
408 for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
409 i = WRAPINCR(i, dh->dh_hlen))
410 if (offset == dh->dh_seqoff)
412 if (offset == dh->dh_seqoff) {
420 dh->dh_seqopt = 0;
423 for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
424 slot = WRAPINCR(slot, dh->dh_hlen)) {
436 DIRHASH_UNLOCK(dh);
444 DIRHASH_UNLOCK(dh);
465 if (dh->dh_seqopt == 0 && dh->dh_seqoff == offset)
466 dh->dh_seqopt = 1;
467 dh->dh_seqoff = offset + LFS_DIRSIZ(fs, dp);
468 DIRHASH_UNLOCK(dh);
475 if (dh->dh_hash == NULL) {
476 DIRHASH_UNLOCK(dh);
486 if (dh->dh_seqopt) {
487 dh->dh_seqopt = 0;
491 DIRHASH_UNLOCK(dh);
518 struct dirhash *dh;
524 if ((dh = ip->i_dirhash) == NULL)
527 DIRHASH_LOCK(dh);
528 if (dh->dh_hash == NULL) {
529 DIRHASH_UNLOCK(dh);
537 if ((dirblock = dh->dh_firstfree[i]) != -1)
540 DIRHASH_UNLOCK(dh);
544 KASSERT(dirblock < dh->dh_nblk &&
545 dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN));
549 DIRHASH_UNLOCK(dh);
555 DIRHASH_UNLOCK(dh);
565 DIRHASH_UNLOCK(dh);
578 DIRHASH_UNLOCK(dh);
586 DIRHASH_UNLOCK(dh);
592 DIRHASH_UNLOCK(dh);
605 struct dirhash *dh;
609 if ((dh = ip->i_dirhash) == NULL)
612 DIRHASH_LOCK(dh);
613 if (dh->dh_hash == NULL) {
614 DIRHASH_UNLOCK(dh);
619 if (dh->dh_blkfree[dh->dh_dirblks - 1] != dirblksiz / DIRALIGN) {
620 DIRHASH_UNLOCK(dh);
624 for (i = dh->dh_dirblks - 1; i >= 0; i--)
625 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
627 DIRHASH_UNLOCK(dh);
640 struct dirhash *dh;
644 if ((dh = ip->i_dirhash) == NULL)
647 DIRHASH_LOCK(dh);
648 if (dh->dh_hash == NULL) {
649 DIRHASH_UNLOCK(dh);
654 KASSERT(offset < dh->dh_dirblks * dirblksiz);
659 if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
660 DIRHASH_UNLOCK(dh);
666 slot = ulfsdirhash_hash(dh, lfs_dir_nameptr(fs, dirp),
668 while (DH_ENTRY(dh, slot) >= 0)
669 slot = WRAPINCR(slot, dh->dh_hlen);
670 if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
671 dh->dh_hused++;
672 DH_ENTRY(dh, slot) = offset;
675 ulfsdirhash_adjfree(dh, offset, -LFS_DIRSIZ(fs, dirp), dirblksiz);
676 DIRHASH_UNLOCK(dh);
688 struct dirhash *dh;
692 if ((dh = ip->i_dirhash) == NULL)
695 DIRHASH_LOCK(dh);
696 if (dh->dh_hash == NULL) {
697 DIRHASH_UNLOCK(dh);
702 KASSERT(offset < dh->dh_dirblks * dirblksiz);
704 slot = ulfsdirhash_findslot(dh, lfs_dir_nameptr(fs, dirp),
708 ulfsdirhash_delslot(dh, slot);
711 ulfsdirhash_adjfree(dh, offset, LFS_DIRSIZ(fs, dirp), dirblksiz);
712 DIRHASH_UNLOCK(dh);
724 struct dirhash *dh;
727 if ((dh = ip->i_dirhash) == NULL)
729 DIRHASH_LOCK(dh);
730 if (dh->dh_hash == NULL) {
731 DIRHASH_UNLOCK(dh);
736 KASSERT(oldoff < dh->dh_dirblks * ip->i_lfs->um_dirblksiz &&
737 newoff < dh->dh_dirblks * ip->i_lfs->um_dirblksiz);
739 slot = ulfsdirhash_findslot(dh, lfs_dir_nameptr(fs, dirp),
741 DH_ENTRY(dh, slot) = newoff;
742 DIRHASH_UNLOCK(dh);
752 struct dirhash *dh;
756 if ((dh = ip->i_dirhash) == NULL)
758 DIRHASH_LOCK(dh);
759 if (dh->dh_hash == NULL) {
760 DIRHASH_UNLOCK(dh);
765 KASSERT(offset == dh->dh_dirblks * dirblksiz);
767 if (block >= dh->dh_nblk) {
769 DIRHASH_UNLOCK(dh);
773 dh->dh_dirblks = block + 1;
776 dh->dh_blkfree[block] = dirblksiz / DIRALIGN;
777 if (dh->dh_firstfree[DH_NFSTATS] == -1)
778 dh->dh_firstfree[DH_NFSTATS] = block;
779 DIRHASH_UNLOCK(dh);
788 struct dirhash *dh;
792 if ((dh = ip->i_dirhash) == NULL)
795 DIRHASH_LOCK(dh);
796 if (dh->dh_hash == NULL) {
797 DIRHASH_UNLOCK(dh);
802 KASSERT(offset <= dh->dh_dirblks * dirblksiz);
810 if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
811 DIRHASH_UNLOCK(dh);
821 if (dh->dh_firstfree[DH_NFSTATS] >= block)
822 dh->dh_firstfree[DH_NFSTATS] = -1;
823 for (i = block; i < dh->dh_dirblks; i++)
824 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
827 if (dh->dh_firstfree[i] >= block)
829 dh->dh_dirblks = block;
830 DIRHASH_UNLOCK(dh);
846 struct dirhash *dh;
853 if ((dh = ip->i_dirhash) == NULL)
856 DIRHASH_LOCK(dh);
857 if (dh->dh_hash == NULL) {
858 DIRHASH_UNLOCK(dh);
864 if ((offset & (dirblksiz - 1)) != 0 || block >= dh->dh_dirblks)
889 ulfsdirhash_findslot(dh, lfs_dir_nameptr(fs, dp),
898 if (dh->dh_blkfree[block] * DIRALIGN != nfree)
903 if (dh->dh_firstfree[i] == block && i != ffslot)
905 if (dh->dh_firstfree[ffslot] == -1)
907 DIRHASH_UNLOCK(dh);
914 ulfsdirhash_hash(struct dirhash *dh, const char *name, int namelen)
925 hash = hash32_buf(&dh, sizeof(dh), hash);
926 return (hash % dh->dh_hlen);
933 * The caller must ensure we have exclusive access to `dh'; normally
938 ulfsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff, int dirblksiz)
942 KASSERT(mutex_owned(&dh->dh_lock));
946 KASSERT(block < dh->dh_nblk && block < dh->dh_dirblks);
947 ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
948 dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
949 nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
954 if (dh->dh_firstfree[ofidx] == block) {
955 for (i = block + 1; i < dh->dh_dirblks; i++)
956 if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
958 dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
962 if (dh->dh_firstfree[nfidx] > block ||
963 dh->dh_firstfree[nfidx] == -1)
964 dh->dh_firstfree[nfidx] = block;
972 * `dh' must be locked on entry and remains so on return.
975 ulfsdirhash_findslot(struct dirhash *dh, const char *name, int namelen,
980 KASSERT(mutex_owned(&dh->dh_lock));
983 KASSERT(dh->dh_hused < dh->dh_hlen);
984 slot = ulfsdirhash_hash(dh, name, namelen);
985 while (DH_ENTRY(dh, slot) != offset &&
986 DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
987 slot = WRAPINCR(slot, dh->dh_hlen);
988 if (DH_ENTRY(dh, slot) != offset)
997 * `dh' must be locked on entry and remains so on return.
1000 ulfsdirhash_delslot(struct dirhash *dh, int slot)
1004 KASSERT(mutex_owned(&dh->dh_lock));
1007 DH_ENTRY(dh, slot) = DIRHASH_DEL;
1010 for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
1011 i = WRAPINCR(i, dh->dh_hlen);
1012 if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
1013 i = WRAPDECR(i, dh->dh_hlen);
1014 while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
1015 DH_ENTRY(dh, i) = DIRHASH_EMPTY;
1016 dh->dh_hused--;
1017 i = WRAPDECR(i, dh->dh_hlen);
1019 KASSERT(dh->dh_hused >= 0);
1066 struct dirhash *dh;
1075 if ((dh = TAILQ_FIRST(&ulfsdirhash_list)) == NULL) {
1079 DIRHASH_LOCK(dh);
1080 KASSERT(dh->dh_hash != NULL);
1083 if (--dh->dh_score > 0) {
1084 DIRHASH_UNLOCK(dh);
1090 TAILQ_REMOVE(&ulfsdirhash_list, dh, dh_list);
1091 dh->dh_onlist = 0;
1092 hash = dh->dh_hash;
1093 hashsz = dh->dh_hashsz;
1094 dh->dh_hash = NULL;
1095 blkfree = dh->dh_blkfree;
1096 blkfreesz = dh->dh_blkfreesz;
1097 dh->dh_blkfree = NULL;
1098 narrays = dh->dh_narrays;
1099 mem = narrays * sizeof(*dh->dh_hash) +
1100 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
1101 dh->dh_nblk * sizeof(*dh->dh_blkfree);
1104 DIRHASH_UNLOCK(dh);
Indexes created Thu Oct 02 01:09:59 GMT 2025