File: [local] / sys / ufs / ufs / dirhash.h (download)
Revision 1.1.1.1 (vendor branch), Tue Mar 4 16:16:19 2008 UTC (16 years, 6 months ago) by nbrk
Branch: OPENBSD_4_2_BASE, MAIN
CVS Tags: jornada-partial-support-wip, HEAD Changes since 1.1: +0 -0 lines
Import of OpenBSD 4.2 release kernel tree with initial code to support
Jornada 720/728, StrongARM 1110-based handheld PC.
At this point kernel roots on NFS and boots into vfs_mountroot() and traps.
What is supported:
- glass console, Jornada framebuffer (jfb) works in 16bpp direct color mode
(needs some palette tweaks for non black/white/blue colors, i think)
- saic, SA11x0 interrupt controller (needs cleanup)
- sacom, SA11x0 UART (supported only as boot console for now)
- SA11x0 GPIO controller fully supported (but can't handle multiple interrupt
handlers on one gpio pin)
- sassp, SSP port on SA11x0 that attaches spibus
- Jornada microcontroller (jmcu) to control kbd, battery, etc throught
the SPI bus (wskbd attaches on jmcu, but not tested)
- tod functions seem work
- initial code for SA-1111 (chip companion) : this is TODO
Next important steps, i think:
- gpio and intc on sa1111
- pcmcia support for sa11x0 (and sa1111 help logic)
- REAL root on nfs when we have PCMCIA support (we may use any of supported pccard NICs)
- root on wd0! (using already supported PCMCIA-ATA)
|
/* $OpenBSD: dirhash.h,v 1.4 2006/04/29 23:09:45 tedu Exp $ */
/*
* Copyright (c) 2001 Ian Dowse. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.4 2003/01/01 18:48:59 schweikh Exp $
*/
#ifndef _UFS_UFS_DIRHASH_H_
#define _UFS_UFS_DIRHASH_H_
#include <sys/rwlock.h>
/*
* For fast operations on large directories, we maintain a hash
* that maps the file name to the offset of the directory entry within
* the directory file.
*
* The hashing uses a dumb spillover to the next free slot on
* collisions, so we must keep the utilisation low to avoid
* long linear searches. Deleted entries that are not the last
* in a chain must be marked DIRHASH_DEL.
*
* We also maintain information about free space in each block
* to speed up creations.
*/
#define DIRHASH_EMPTY (-1) /* entry unused */
#define DIRHASH_DEL (-2) /* deleted entry; may be part of chain */
#define DIRALIGN 4
#define DH_NFSTATS (DIRECTSIZ(MAXNAMLEN + 1) / DIRALIGN)
/* max DIRALIGN words in a directory entry */
/*
* Dirhash uses a score mechanism to achieve a hybrid between a
* least-recently-used and a least-often-used algorithm for entry
* recycling. The score is incremented when a directory is used, and
* decremented when the directory is a candidate for recycling. When
* the score reaches zero, the hash is recycled. Hashes are linked
* together on a TAILQ list, and hashes with higher scores filter
* towards the tail (most recently used) end of the list.
*
* New hash entries are given an inital score of DH_SCOREINIT and are
* placed at the most-recently-used end of the list. This helps a lot
* in the worst-case case scenario where every directory access is
* to a directory that is not hashed (i.e. the working set of hash
* candidates is much larger than the configured memry limit). In this
* case it limits the number of hash builds to 1/DH_SCOREINIT of the
* number of accesses.
*/
#define DH_SCOREINIT 8 /* initial dh_score when dirhash built */
#define DH_SCOREMAX 64 /* max dh_score value */
/*
* The main hash table has 2 levels. It is an array of pointers to
* blocks of DH_NBLKOFF offsets.
*/
#define DH_BLKOFFSHIFT 8
#define DH_NBLKOFF (1 << DH_BLKOFFSHIFT)
#define DH_BLKOFFMASK (DH_NBLKOFF - 1)
#define DH_ENTRY(dh, slot) \
((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])
struct dirhash {
doff_t **dh_hash; /* the hash array (2-level) */
int dh_narrays; /* number of entries in dh_hash */
int dh_hlen; /* total slots in the 2-level hash array */
int dh_hused; /* entries in use */
/* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
u_int8_t *dh_blkfree; /* free DIRALIGN words in each dir block */
int dh_nblk; /* size of dh_blkfree array */
int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */
int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */
int dh_seqopt; /* sequential access optimisation enabled */
doff_t dh_seqoff; /* sequential access optimisation offset */
int dh_score; /* access count for this dirhash */
int dh_onlist; /* true if on the ufsdirhash_list chain */
/* Protected by ufsdirhash_mtx. */
TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */
};
extern int ufs_mindirhashsize;
extern int ufs_dirhashmaxmem;
extern int ufs_dirhashmem;
/*
* Dirhash functions.
*/
void ufsdirhash_init(void);
void ufsdirhash_uninit(void);
int ufsdirhash_build(struct inode *);
doff_t ufsdirhash_findfree(struct inode *, int, int *);
doff_t ufsdirhash_enduseful(struct inode *);
int ufsdirhash_lookup(struct inode *, char *, int, doff_t *, struct buf **,
doff_t *);
void ufsdirhash_newblk(struct inode *, doff_t);
void ufsdirhash_add(struct inode *, struct direct *, doff_t);
void ufsdirhash_remove(struct inode *, struct direct *, doff_t);
void ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
void ufsdirhash_dirtrunc(struct inode *, doff_t);
void ufsdirhash_free(struct inode *);
void ufsdirhash_checkblock(struct inode *, char *, doff_t);
#endif /* !_UFS_UFS_DIRHASH_H_ */