Lines Matching refs:dh
68 static int ufsdirhash_hash(struct dirhash *dh, const char *name, int namelen);
69 static void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff,
71 static void ufsdirhash_delslot(struct dirhash *dh, int slot);
72 static int ufsdirhash_findslot(struct dirhash *dh, const char *name,
83 #define DIRHASH_LOCK(dh) mutex_enter(&(dh)->dh_lock)
84 #define DIRHASH_UNLOCK(dh) mutex_exit(&(dh)->dh_lock)
115 struct dirhash *dh;
156 memreqd = sizeof(*dh) + narrays * sizeof(*dh->dh_hash) +
157 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
158 nblocks * sizeof(*dh->dh_blkfree);
176 dh = pool_cache_get(ufsdirhash_cache, PR_NOWAIT);
177 if (dh == NULL) {
181 memset(dh, 0, sizeof(*dh));
182 mutex_init(&dh->dh_lock, MUTEX_DEFAULT, IPL_NONE);
183 DIRHASH_LOCK(dh);
184 dh->dh_hashsz = narrays * sizeof(dh->dh_hash[0]);
185 dh->dh_hash = kmem_zalloc(dh->dh_hashsz, KM_NOSLEEP);
186 dh->dh_blkfreesz = nblocks * sizeof(dh->dh_blkfree[0]);
187 dh->dh_blkfree = kmem_zalloc(dh->dh_blkfreesz, KM_NOSLEEP);
188 if (dh->dh_hash == NULL || dh->dh_blkfree == NULL)
191 if ((dh->dh_hash[i] = DIRHASH_BLKALLOC()) == NULL)
194 dh->dh_hash[i][j] = DIRHASH_EMPTY;
198 dh->dh_narrays = narrays;
199 dh->dh_hlen = nslots;
200 dh->dh_nblk = nblocks;
201 dh->dh_dirblks = dirblocks;
203 dh->dh_blkfree[i] = dirblksiz / DIRALIGN;
205 dh->dh_firstfree[i] = -1;
206 dh->dh_firstfree[DH_NFSTATS] = 0;
207 dh->dh_seqopt = 0;
208 dh->dh_seqoff = 0;
209 dh->dh_score = DH_SCOREINIT;
210 ip->i_dirhash = dh;
237 slot = ufsdirhash_hash(dh, ep->d_name, ep->d_namlen);
238 while (DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
239 slot = WRAPINCR(slot, dh->dh_hlen);
240 dh->dh_hused++;
241 DH_ENTRY(dh, slot) = pos;
242 ufsdirhash_adjfree(dh, pos, -DIRSIZ(0, ep, needswap),
251 TAILQ_INSERT_TAIL(&ufsdirhash_list, dh, dh_list);
252 dh->dh_onlist = 1;
253 DIRHASH_UNLOCK(dh);
258 DIRHASH_UNLOCK(dh);
259 if (dh->dh_hash != NULL) {
261 if (dh->dh_hash[i] != NULL)
262 DIRHASH_BLKFREE(dh->dh_hash[i]);
263 kmem_free(dh->dh_hash, dh->dh_hashsz);
265 if (dh->dh_blkfree != NULL)
266 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
267 mutex_destroy(&dh->dh_lock);
268 pool_cache_put(ufsdirhash_cache, dh);
280 struct dirhash *dh;
283 if ((dh = ip->i_dirhash) == NULL)
286 if (dh->dh_onlist) {
288 if (dh->dh_onlist)
289 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
293 /* The dirhash pointed to by 'dh' is exclusively ours now. */
294 mem = sizeof(*dh);
295 if (dh->dh_hash != NULL) {
296 for (i = 0; i < dh->dh_narrays; i++)
297 DIRHASH_BLKFREE(dh->dh_hash[i]);
298 kmem_free(dh->dh_hash, dh->dh_hashsz);
299 kmem_free(dh->dh_blkfree, dh->dh_blkfreesz);
300 mem += dh->dh_hashsz;
301 mem += dh->dh_narrays * DH_NBLKOFF * sizeof(**dh->dh_hash);
302 mem += dh->dh_nblk * sizeof(*dh->dh_blkfree);
304 mutex_destroy(&dh->dh_lock);
305 pool_cache_put(ufsdirhash_cache, dh);
326 struct dirhash *dh, *dh_next;
335 if ((dh = ip->i_dirhash) == NULL)
346 if (TAILQ_NEXT(dh, dh_list) != NULL) {
348 DIRHASH_LOCK(dh);
355 if (dh->dh_hash != NULL &&
356 (dh_next = TAILQ_NEXT(dh, dh_list)) != NULL &&
357 dh->dh_score >= dh_next->dh_score) {
358 KASSERT(dh->dh_onlist);
359 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
360 TAILQ_INSERT_AFTER(&ufsdirhash_list, dh_next, dh,
366 DIRHASH_LOCK(dh);
368 if (dh->dh_hash == NULL) {
369 DIRHASH_UNLOCK(dh);
375 if (dh->dh_score < DH_SCOREMAX)
376 dh->dh_score++;
383 slot = ufsdirhash_hash(dh, name, namelen);
385 if (dh->dh_seqopt) {
392 for (i = slot; (offset = DH_ENTRY(dh, i)) != DIRHASH_EMPTY;
393 i = WRAPINCR(i, dh->dh_hlen))
394 if (offset == dh->dh_seqoff)
396 if (offset == dh->dh_seqoff) {
404 dh->dh_seqopt = 0;
407 for (; (offset = DH_ENTRY(dh, slot)) != DIRHASH_EMPTY;
408 slot = WRAPINCR(slot, dh->dh_hlen)) {
420 DIRHASH_UNLOCK(dh);
428 DIRHASH_UNLOCK(dh);
449 if (dh->dh_seqopt == 0 && dh->dh_seqoff == offset)
450 dh->dh_seqopt = 1;
451 dh->dh_seqoff = offset + DIRSIZ(0, dp, needswap);
452 DIRHASH_UNLOCK(dh);
459 if (dh->dh_hash == NULL) {
460 DIRHASH_UNLOCK(dh);
470 if (dh->dh_seqopt) {
471 dh->dh_seqopt = 0;
475 DIRHASH_UNLOCK(dh);
501 struct dirhash *dh;
508 if ((dh = ip->i_dirhash) == NULL)
511 DIRHASH_LOCK(dh);
512 if (dh->dh_hash == NULL) {
513 DIRHASH_UNLOCK(dh);
521 if ((dirblock = dh->dh_firstfree[i]) != -1)
524 DIRHASH_UNLOCK(dh);
528 KASSERT(dirblock < dh->dh_nblk &&
529 dh->dh_blkfree[dirblock] >= howmany(slotneeded, DIRALIGN));
533 DIRHASH_UNLOCK(dh);
539 DIRHASH_UNLOCK(dh);
549 DIRHASH_UNLOCK(dh);
562 DIRHASH_UNLOCK(dh);
570 DIRHASH_UNLOCK(dh);
576 DIRHASH_UNLOCK(dh);
589 struct dirhash *dh;
593 if ((dh = ip->i_dirhash) == NULL)
596 DIRHASH_LOCK(dh);
597 if (dh->dh_hash == NULL) {
598 DIRHASH_UNLOCK(dh);
603 if (dh->dh_blkfree[dh->dh_dirblks - 1] != dirblksiz / DIRALIGN) {
604 DIRHASH_UNLOCK(dh);
608 for (i = dh->dh_dirblks - 1; i >= 0; i--)
609 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
611 DIRHASH_UNLOCK(dh);
623 struct dirhash *dh;
628 if ((dh = ip->i_dirhash) == NULL)
631 DIRHASH_LOCK(dh);
632 if (dh->dh_hash == NULL) {
633 DIRHASH_UNLOCK(dh);
638 KASSERT(offset < dh->dh_dirblks * dirblksiz);
643 if (dh->dh_hused >= (dh->dh_hlen * 3) / 4) {
644 DIRHASH_UNLOCK(dh);
650 slot = ufsdirhash_hash(dh, dirp->d_name, dirp->d_namlen);
651 while (DH_ENTRY(dh, slot) >= 0)
652 slot = WRAPINCR(slot, dh->dh_hlen);
653 if (DH_ENTRY(dh, slot) == DIRHASH_EMPTY)
654 dh->dh_hused++;
655 DH_ENTRY(dh, slot) = offset;
658 ufsdirhash_adjfree(dh, offset, -DIRSIZ(0, dirp, needswap), dirblksiz);
659 DIRHASH_UNLOCK(dh);
670 struct dirhash *dh;
675 if ((dh = ip->i_dirhash) == NULL)
678 DIRHASH_LOCK(dh);
679 if (dh->dh_hash == NULL) {
680 DIRHASH_UNLOCK(dh);
685 KASSERT(offset < dh->dh_dirblks * dirblksiz);
687 slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, offset);
690 ufsdirhash_delslot(dh, slot);
693 ufsdirhash_adjfree(dh, offset, DIRSIZ(0, dirp, needswap), dirblksiz);
694 DIRHASH_UNLOCK(dh);
705 struct dirhash *dh;
708 if ((dh = ip->i_dirhash) == NULL)
710 DIRHASH_LOCK(dh);
711 if (dh->dh_hash == NULL) {
712 DIRHASH_UNLOCK(dh);
717 KASSERT(oldoff < dh->dh_dirblks * ip->i_ump->um_dirblksiz &&
718 newoff < dh->dh_dirblks * ip->i_ump->um_dirblksiz);
720 slot = ufsdirhash_findslot(dh, dirp->d_name, dirp->d_namlen, oldoff);
721 DH_ENTRY(dh, slot) = newoff;
722 DIRHASH_UNLOCK(dh);
732 struct dirhash *dh;
736 if ((dh = ip->i_dirhash) == NULL)
738 DIRHASH_LOCK(dh);
739 if (dh->dh_hash == NULL) {
740 DIRHASH_UNLOCK(dh);
745 KASSERT(offset == dh->dh_dirblks * dirblksiz);
747 if (block >= dh->dh_nblk) {
749 DIRHASH_UNLOCK(dh);
753 dh->dh_dirblks = block + 1;
756 dh->dh_blkfree[block] = dirblksiz / DIRALIGN;
757 if (dh->dh_firstfree[DH_NFSTATS] == -1)
758 dh->dh_firstfree[DH_NFSTATS] = block;
759 DIRHASH_UNLOCK(dh);
768 struct dirhash *dh;
772 if ((dh = ip->i_dirhash) == NULL)
775 DIRHASH_LOCK(dh);
776 if (dh->dh_hash == NULL) {
777 DIRHASH_UNLOCK(dh);
782 KASSERT(offset <= dh->dh_dirblks * dirblksiz);
790 if (block < dh->dh_nblk / 8 && dh->dh_narrays > 1) {
791 DIRHASH_UNLOCK(dh);
801 if (dh->dh_firstfree[DH_NFSTATS] >= block)
802 dh->dh_firstfree[DH_NFSTATS] = -1;
803 for (i = block; i < dh->dh_dirblks; i++)
804 if (dh->dh_blkfree[i] != dirblksiz / DIRALIGN)
807 if (dh->dh_firstfree[i] >= block)
809 dh->dh_dirblks = block;
810 DIRHASH_UNLOCK(dh);
825 struct dirhash *dh;
833 if ((dh = ip->i_dirhash) == NULL)
836 DIRHASH_LOCK(dh);
837 if (dh->dh_hash == NULL) {
838 DIRHASH_UNLOCK(dh);
844 if ((offset & (dirblksiz - 1)) != 0 || block >= dh->dh_dirblks)
869 ufsdirhash_findslot(dh, dp->d_name, dp->d_namlen, offset + i);
876 if (dh->dh_blkfree[block] * DIRALIGN != nfree)
881 if (dh->dh_firstfree[i] == block && i != ffslot)
883 if (dh->dh_firstfree[ffslot] == -1)
885 DIRHASH_UNLOCK(dh);
892 ufsdirhash_hash(struct dirhash *dh, const char *name, int namelen)
903 hash = hash32_buf(&dh, sizeof(dh), hash);
904 return (hash % dh->dh_hlen);
911 * The caller must ensure we have exclusive access to `dh'; normally
916 ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff, int dirblksiz)
920 KASSERT(mutex_owned(&dh->dh_lock));
924 KASSERT(block < dh->dh_nblk && block < dh->dh_dirblks);
925 ofidx = BLKFREE2IDX(dh->dh_blkfree[block]);
926 dh->dh_blkfree[block] = (int)dh->dh_blkfree[block] + (diff / DIRALIGN);
927 nfidx = BLKFREE2IDX(dh->dh_blkfree[block]);
932 if (dh->dh_firstfree[ofidx] == block) {
933 for (i = block + 1; i < dh->dh_dirblks; i++)
934 if (BLKFREE2IDX(dh->dh_blkfree[i]) == ofidx)
936 dh->dh_firstfree[ofidx] = (i < dh->dh_dirblks) ? i : -1;
940 if (dh->dh_firstfree[nfidx] > block ||
941 dh->dh_firstfree[nfidx] == -1)
942 dh->dh_firstfree[nfidx] = block;
950 * `dh' must be locked on entry and remains so on return.
953 ufsdirhash_findslot(struct dirhash *dh, const char *name, int namelen,
958 KASSERT(mutex_owned(&dh->dh_lock));
961 KASSERT(dh->dh_hused < dh->dh_hlen);
962 slot = ufsdirhash_hash(dh, name, namelen);
963 while (DH_ENTRY(dh, slot) != offset &&
964 DH_ENTRY(dh, slot) != DIRHASH_EMPTY)
965 slot = WRAPINCR(slot, dh->dh_hlen);
966 if (DH_ENTRY(dh, slot) != offset)
975 * `dh' must be locked on entry and remains so on return.
978 ufsdirhash_delslot(struct dirhash *dh, int slot)
982 KASSERT(mutex_owned(&dh->dh_lock));
985 DH_ENTRY(dh, slot) = DIRHASH_DEL;
988 for (i = slot; DH_ENTRY(dh, i) == DIRHASH_DEL; )
989 i = WRAPINCR(i, dh->dh_hlen);
990 if (DH_ENTRY(dh, i) == DIRHASH_EMPTY) {
991 i = WRAPDECR(i, dh->dh_hlen);
992 while (DH_ENTRY(dh, i) == DIRHASH_DEL) {
993 DH_ENTRY(dh, i) = DIRHASH_EMPTY;
994 dh->dh_hused--;
995 i = WRAPDECR(i, dh->dh_hlen);
997 KASSERT(dh->dh_hused >= 0);
1041 struct dirhash *dh;
1050 if ((dh = TAILQ_FIRST(&ufsdirhash_list)) == NULL) {
1054 DIRHASH_LOCK(dh);
1055 KASSERT(dh->dh_hash != NULL);
1058 if (--dh->dh_score > 0) {
1059 DIRHASH_UNLOCK(dh);
1065 TAILQ_REMOVE(&ufsdirhash_list, dh, dh_list);
1066 dh->dh_onlist = 0;
1067 hash = dh->dh_hash;
1068 hashsz = dh->dh_hashsz;
1069 dh->dh_hash = NULL;
1070 blkfree = dh->dh_blkfree;
1071 blkfreesz = dh->dh_blkfreesz;
1072 dh->dh_blkfree = NULL;
1073 narrays = dh->dh_narrays;
1074 mem = narrays * sizeof(*dh->dh_hash) +
1075 narrays * DH_NBLKOFF * sizeof(**dh->dh_hash) +
1076 dh->dh_nblk * sizeof(*dh->dh_blkfree);
1079 DIRHASH_UNLOCK(dh);