From bec02e93bf31d7ce54724691448fb158a07d2632 Mon Sep 17 00:00:00 2001
From: "H. Peter Anvin" <hpa@zytor.com>
Date: Thu, 1 Feb 2007 22:11:12 -0800
Subject: [PATCH] Use LRU caching instead of LRR (least recently read)

---
 cache.inc | 83 +++++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 57 insertions(+), 26 deletions(-)

diff --git a/cache.inc b/cache.inc
index e2595a2..8d471bf 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
+
-- 
2.7.4