aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2007-02-01 22:11:12 -0800
committerH. Peter Anvin <hpa@zytor.com>2007-02-01 22:11:12 -0800
commitbec02e93bf31d7ce54724691448fb158a07d2632 (patch)
tree1c3daec2da2210bb43e4e9711beffa1b347acac6
parentacd7bcea0b3d07c48cdd7af1de2fdacb7604b409 (diff)
downloadsyslinux-elf-bec02e93bf31d7ce54724691448fb158a07d2632.tar.gz
syslinux-elf-bec02e93bf31d7ce54724691448fb158a07d2632.tar.xz
syslinux-elf-bec02e93bf31d7ce54724691448fb158a07d2632.zip
Use LRU caching instead of LRR (least recently read)
-rw-r--r--cache.inc83
1 files changed, 57 insertions, 26 deletions
diff --git a/cache.inc b/cache.inc
index e2595a21..8d471bf6 100644
--- a/cache.inc
+++ b/cache.inc
@@ -1,6 +1,6 @@
; -*- fundamental -*- ---------------------------------------------------
;
-; Copyright 2004 H. Peter Anvin - All Rights Reserved
+; Copyright 2004-2007 H. Peter Anvin - All Rights Reserved
;
; This program is free software; you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
@@ -11,17 +11,32 @@
; -----------------------------------------------------------------------
section .text
+
+ struc cptr
+.sector: resd 1 ; Sector number
+.prev: resw 1 ; LRU pointer to previous (less recent)
+.next: resw 1 ; LRU pointer to next (more recent)
+ endstruc
+cptr_size_lg2 equ 3
+
+NCacheEntries equ 65536/SECTOR_SIZE
+
;
; initcache: Initialize the cache data structures
;
initcache:
xor eax,eax ; We don't care about sector 0
mov di,CachePtrs
- mov cx,65536/SECTOR_SIZE
- rep stosd
+ mov cx,NCacheEntries+1
+ mov bx,CachePtrs+NCacheEntries*cptr_size ; "prev" pointer
+.loop:
+ mov [di+cptr.sector],eax ; Zero sector number
+ mov [di+cptr.prev],bx ; Previous pointer
+ mov [bx+cptr.next],di ; Previous entry's next pointer
+ add di,cptr_size
+ loop .loop
ret
-
;
; getcachesector: Check for a particular sector (EAX) in the sector cache,
; and if it is already there, return a pointer in GS:SI
@@ -31,32 +46,28 @@ initcache:
;
getcachesector:
push cx
+ push bx
+ push di
mov si,cache_seg
mov gs,si
- mov si,CachePtrs ; Sector cache pointers
- mov cx,65536/SECTOR_SIZE
+ mov si,CachePtrs+cptr_size ; Real sector cache pointers
+ mov cx,NCacheEntries
.search:
cmp eax,[si]
jz .hit
- add si,4
+ add si,cptr_size
loop .search
.miss:
TRACER 'M'
- ; Need to load it. Highly inefficient cache replacement
- ; algorithm: Least Recently Written (LRW)
- push bx
+ ; Need to load it.
push es
push gs
pop es
- mov bx,[NextCacheSlot]
- inc bx
- and bx,(1 << (16-SECTOR_SHIFT))-1
- mov [NextCacheSlot],bx
- shl bx,2
- mov [CachePtrs+bx],eax
- shl bx,SECTOR_SHIFT-2
+ mov bx,[CachePtrs+cptr.next] ; "Next most recent than head node"
mov si,bx
+ sub bx,CachePtrs+cptr_size
+ shl bx,SECTOR_SHIFT-cptr_size_lg2 ; Buffer address
pushad
%if IS_EXTLINUX
call getonesec_ext
@@ -65,18 +76,38 @@ getcachesector:
%endif
popad
pop es
- pop bx
- pop cx
- ret
-
-.hit: ; We have it; get the pointer
+.hit:
+ ; Update LRU, then compute buffer address
TRACER 'H'
- sub si,CachePtrs
- shl si,SECTOR_SHIFT-2
+
+ ; Remove from current position in the list
+ mov bx,[si+cptr.prev]
+ mov di,[si+cptr.next]
+ mov [bx+cptr.next],di
+ mov [di+cptr.prev],bx
+
+ ; Add to just before head node
+ mov bx,[CachePtrs+cptr.prev]
+ mov [si+cptr.prev],bx
+ mov [bx+cptr.next],si
+ mov [CachePtrs+cptr.prev],si
+ mov word [si+cptr.next],CachePtrs
+
+ sub si,CachePtrs+cptr_size
+ shl si,SECTOR_SHIFT-cptr_size_lg2 ; Buffer address
+
+ pop di
+ pop bx
pop cx
ret
section .latebss
+
+ ; Each CachePtr contains:
+ ; - Block pointer
+ ; - LRU previous pointer
+ ; - LRU next pointer
+ ; The first entry is the head node of the list
alignb 4
-CachePtrs resd 65536/SECTOR_SIZE ; Cached sector pointers
-NextCacheSlot resw 1 ; Next cache slot to occupy
+CachePtrs resb (NCacheEntries+1)*cptr_size
+