As promised here is my work in progress fuzzy hash VMA lookup stuff.
Actually, two months ago I sat down for an hour or so and tried to do
all the 2.1.x changes necessary to do a complete job of it, alas not
only did I get distracted before finishing, I also cannot find the
half done patch I saved somewhere (hmph...).
Anyways, the following is enough to demonstrate how the layout would
look and how each fundamental operation on the data structure needs to
be implemented. I suppose someone with Linux VM experience could
implant the following ideas into their skull and have something at
least half working in a day or two.
The fuzzy hashing scheme used here was first formulated by Thomas
Schoebel, I fixed all the minor quirks and bugs in his initial
formulation and together we converged on the algorithm as used here.
To my knowledge it is the only hashing scheme which can handle range
based lookups and multiple keys in this manner. (As an interesting
side note, this scheme could be very useful for other applications,
for example a c++ exception handling implementation could make good
use of it with careful crafting).
The reason I like this scheme so much compared to any other VMA lookup
engine is that I _know_ that if the full work is implemented properly
it will be as fast or cheaper _even_ in the common case than what we
have now. Sort of like scalability at no latency cost, the best
kind. (I know there is a slight space cost, and I'm not trying to
ignore that issue, yet I believe this cost to be on the same scale as
that incurred by the old AVL trees)
Enjoy.
#define NULL ((void *)0)
typedef unsigned long pgd_t;
struct semaphore {
unsigned long count1, count2;
};
#define MM_MMAP_HASHSZ 16
struct mm_struct {
struct vm_area_struct *mmap_hash[MM_MMAP_HASHSZ];
struct vm_area_struct *mmap_cache;
struct vm_area_struct *mmap_neighbours;
pgd_t *pgd;
int count, map_count;
struct semaphore mmap_sem;
unsigned long context;
unsigned long start_code, end_code, start_data, end_data;
unsigned long start_brk, brk, start_stack;
unsigned long arg_start, arg_end, env_start, env_end;
unsigned long rss, total_vm, locked_vm;
unsigned long def_flags;
unsigned long cpu_vm_mask;
/*
* This is an architecture-specific pointer: the portable
* part of Linux does not know about any segments.
*/
void * segments;
};
typedef unsigned long pgprot_t;
struct vm_operations_struct;
struct vm_area_struct {
/*0x00*/unsigned long vm_start;
/*0x08*/unsigned long vm_end;
/*0x10*/struct vm_area_struct *vm_hash_next;
/*0x18*/struct vm_area_struct *vm_neighbour_next;
/*0x20*/unsigned long vm_offset;
/*0x28*/unsigned short vm_flags;
/*0x30*/struct mm_struct *vm_mm;
/*0x38*/struct vm_operations_struct *vm_ops;
/*0x40*/pgprot_t vm_page_prot;
/*0x48*/struct file *vm_file;
/*0x50*/struct vm_area_struct **vm_hash_pprev;
/*0x58*/struct vm_area_struct **vm_neighbour_pprev;
/* For areas with inode, the list inode->i_mmap, for shm areas,
* the list of attaches, otherwise unused.
*/
/*0x60*/struct vm_area_struct *vm_next_share;
/*0x68*/struct vm_area_struct **vm_pprev_share;
/*0x70*/unsigned long vm_pte; /* shared mem */
};
#define vmahash(__addr_key) (((__addr_key)>>13) & (MM_MMAP_HASHSZ - 1))
/* The main search engine is not expanded inline everywhere. */
struct vm_area_struct *__find_vma(struct mm_struct *mm, unsigned long addr)
{
struct vm_area_struct *vma;
unsigned int hash = vmahash(addr);
unsigned int starthash = hash;
do { vma = mm->mmap_hash[hash];
if((vma != NULL) && (vma->vm_start > addr))
goto start_search;
hash = ((hash - 1) & (MM_MMAP_HASHSZ - 1));
} while(hash != starthash);
return mm->mmap_neighbours;
start_search:
/* Here is where things get interesting. */
while(1) {
struct vm_area_struct *tmp = vma->vm_hash_next;
if((tmp != NULL) && (tmp->vm_start > addr)) {
vma = tmp;
} else if(((tmp = vma->vm_neighbour_next) != NULL) &&
(tmp->vm_start > addr)) {
vma = tmp;
} else {
vma = vma->vm_neighbour_next;
break;
}
}
return vma;
}
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
struct vm_area_struct *vma = NULL;
if(mm) {
/* Check cache inline quickly.
*
* Sad point: The mmap cache doesn't work for stack
* growth faults, a fix would be welcome. -DaveM
*/
vma = mm->mmap_cache;
if(vma == NULL ||
(vma->vm_end <= addr) ||
(vma->vm_start > addr))
mm->mmap_cache =
vma =
__find_vma(mm, addr);
}
return vma;
}
static __inline__ void vma_insert_neighbour(struct mm_struct *mm, struct vm_area_struct *vma)
{
struct vm_area_struct **vpp = &mm->mmap_neighbours;
unsigned long start = vma->vm_start;
for( ; *vpp && (*vpp)->vm_start > start; vpp = &(*vpp)->vm_neighbour_next)
;
if((vma->vm_neighbour_next = *vpp) != NULL)
(*vpp)->vm_neighbour_pprev = &vma->vm_neighbour_next;
*vpp = vma;
vma->vm_neighbour_pprev = vpp;
}
static __inline__ void vma_insert_hash(struct mm_struct *mm, struct vm_area_struct *vma)
{
unsigned long start = vma->vm_start;
struct vm_area_struct **vpp = &mm->mmap_hash[vmahash(start)];
for( ; *vpp && (*vpp)->vm_start > start; vpp = &(*vpp)->vm_hash_next)
;
if((vma->vm_hash_next = *vpp) != NULL)
(*vpp)->vm_hash_pprev = &vma->vm_hash_next;
*vpp = vma;
vma->vm_hash_pprev = vpp;
}
void vma_insert(struct mm_struct *mm, struct vm_area_struct *vma)
{
vma_insert_neighbour(mm, vma);
vma_insert_hash(mm, vma);
}
void vma_remove(struct vm_area_struct *vma)
{
struct vm_area_struct *n_next = vma->vm_neighbour_next;
struct vm_area_struct *h_next = vma->vm_hash_next;
if(n_next) n_next->vm_neighbour_pprev = vma->vm_neighbour_pprev;
if(h_next) h_next->vm_hash_pprev = vma->vm_hash_pprev;
*vma->vm_neighbour_pprev = n_next;
*vma->vm_hash_pprev = h_next;
}
On Tue, 25 Aug 1998 01:33:14 -0700,
"David S. Miller" <[email protected]> wrote:
>As promised here is my work in progress fuzzy hash VMA lookup stuff.
>
>The fuzzy hashing scheme used here was first formulated by Thomas
>Schoebel, I fixed all the minor quirks and bugs in his initial
>formulation and together we converged on the algorithm as used here.
Lots of code with very few comments snipped. Come on Davem, make it
understandable for us mere mortals. If it took two people to fix
quirks and bugs and converge the algorithm, surely a few notes on how
it works would not go astray.
"David S. Miller" <[email protected]> wrote:
>As promised here is my work in progress fuzzy hash VMA lookup stuff.
On Tue, Aug 25, 1998 at 10:47:26PM +1000, Keith Owens wrote:
> Lots of code with very few comments snipped. Come on Davem, make it
> understandable for us mere mortals. If it took two people to fix
> quirks and bugs and converge the algorithm, surely a few notes on how
> it works would not go astray.
Nope, I can't see how it works either.
BTW, a splay tree would also be as fast as what we have now in the
common case, without need for a special one entry cache. The root of
the tree automatically acts as the cache.
-- Jamie
Hi,
I've managed a draft version of the fuzzy hash VMA lookup stuff to work.
Right now it works only on i386.
It would be nice to know the speed of ElectricFence programs
with the patch applied.
BTW, I've also reimplemented one slot cache to catch growing down
areas too. However the cache requires find_vma calls
to be atomic against each other. I suppose it's true for now, isn't it?
I also measured the one slot cache hit rate.
On my system it stays permanently about 1/3rd!
Best wishes
Andrey V.
Savochkin
On Tue, Aug 25, 1998 at 01:33:14AM -0700, David S. Miller wrote:
>
> As promised here is my work in progress fuzzy hash VMA lookup stuff.
>
> Actually, two months ago I sat down for an hour or so and tried to do
> all the 2.1.x changes necessary to do a complete job of it, alas not
> only did I get distracted before finishing, I also cannot find the
> half done patch I saved somewhere (hmph...).
>
> Anyways, the following is enough to demonstrate how the layout would
> look and how each fundamental operation on the data structure needs to
> be implemented. I suppose someone with Linux VM experience could
> implant the following ideas into their skull and have something at
> least half working in a day or two.
>
> The fuzzy hashing scheme used here was first formulated by Thomas
> Schoebel, I fixed all the minor quirks and bugs in his initial
> formulation and together we converged on the algorithm as used here.
> To my knowledge it is the only hashing scheme which can handle range
> based lookups and multiple keys in this manner. (As an interesting
> side note, this scheme could be very useful for other applications,
> for example a c++ exception handling implementation could make good
> use of it with careful crafting).
>
> The reason I like this scheme so much compared to any other VMA lookup
> engine is that I _know_ that if the full work is implemented properly
> it will be as fast or cheaper _even_ in the common case than what we
> have now. Sort of like scalability at no latency cost, the best
> kind. (I know there is a slight space cost, and I'm not trying to
> ignore that issue, yet I believe this cost to be on the same scale as
> that incurred by the old AVL trees)