/* Copyright 1999 Element 14 Ltd
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
*
* NameCache.c -- Long filename cacheing using circular buffer
*
* 05-02-99 sbrodie Original
*/
/* Test program builds with:
*
* cc -ITCPIPLibs: -DLONGNAMES -DTEST -Wpc NameCache.c
*
*/
/* This file implements a circular buffer for temporarily storing search records
* from a search operation. The directory name and the returned block of data
* are stored and returned if the data for the same object is requested again.
* The cache is flushed on exit from each FileSwitch entry point to ensure
* cache consistency.
*
* Each record is word-aligned and starts with a rec_hdr structure. The dirname
* char array is variable length and is rounded up to make the structure an exact
* number of words long. This is followed immediately by the variable length record
* returned by the server (23 bytes header, plus the leafname). Again, the size of
* this is rounded up to the next word boundary. A complete record is never split
* over the end of the buffer. The rec_hdr.offset_next value is the offset from the
* start of the rec_hdr to the start of the next rec_hdr. The value is in bytes.
* The value may be negative if the next entry starts at the beginning of the buffer.
* The rec_hdr.offset_data value is -1 if the record does not hold a valid entry.
* NameCache.last is -1 if there are no valid records at all, otherwise it is the
* offset from the start of the buffer to the most recently added item (ie. the
* one whose offset_next gives the location of NameCache.head. This is used for
* maintaining the chain of records.
*/
/* Standard includes */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <ctype.h>
#include "kernel.h"
/* Our includes */
#include "stdtypes.h"
#include "NameCache.h"
#ifndef LONGNAMES
BYTE *NameCache_Locate(const char *filename)
{
(void) filename;
return NULL;
}
void NameCache_Add(const char *dirname, BYTE *b)
{
(void) dirname;
(void) b;
}
void NameCache_Flush(ncf_reason why)
{
(void) why;
}
void NameCache_Init(void)
{
}
#else
static struct {
BYTE *data;
int head;
int tail;
int last;
int hits;
} NameCache;
typedef struct {
int offset_next;
int offset_data;
char dirbase[1];
} rec_hdr;
static const size_t cachesize = 4096;
static void NameCache_Exit(void)
{
free(NameCache.data);
NameCache.data = NULL;
}
void NameCache_Flush(ncf_reason why)
{
debug2("NameCacheFlush(reason = %d) hits %d\n", why, NameCache.hits);
if (why == ncf_REINIT) NameCache.hits = 0;
if (NameCache.data) {
NameCache.head = 0;
NameCache.tail = 0;
NameCache.last = -1;
((rec_hdr *) NameCache.data) -> offset_next = -1;
}
}
void NameCache_Init(void)
{
NameCache.data = calloc(1, cachesize);
if (NameCache.data != 0) {
atexit(NameCache_Exit);
}
NameCache_Flush(ncf_REINIT);
}
BYTE *NameCache_Locate(const char *filename)
{
rec_hdr *hdr;
int offset = NameCache.tail;
if (NameCache.data == NULL || NameCache.last == -1) return NULL;
for (;;offset += hdr->offset_next) {
hdr = (rec_hdr *)(NameCache.data + offset);
if (hdr->offset_data == -1) {
if (offset == NameCache.head) break;
}
else {
BYTE *res = NameCache.data + offset + hdr->offset_data;
const size_t baselen = strlen(hdr->dirbase);
if (filename[baselen-1] == '\\')
if (!strcmp((char *)res+23, filename + baselen))
if (!strncmp(hdr->dirbase, filename, baselen)) {
/* Found match */
debug1("NameCache: returning match for `%s'\n", filename);
++NameCache.hits;
return res;
}
}
}
return NULL;
}
static void NameCache_Trim(void)
{
/* Any deleted entries at tail of queue - dump them */
while (NameCache.tail != NameCache.head) {
rec_hdr *tailp = (rec_hdr *) (NameCache.data + NameCache.tail);
if (tailp->offset_data != -1) {
break;
}
NameCache.tail += tailp->offset_next;
}
if (NameCache.tail == NameCache.head) {
/* Empty */
debug0("Reset cache\n");
NameCache.last = -1;
NameCache.tail = NameCache.head = 0;
((rec_hdr *) (NameCache.data))->offset_data = -1;
}
}
void NameCache_Add(const char *dirname, BYTE *b)
{
/* Calculate size of record data, directory name, and
* management overhead.
*/
static const size_t overhead = offsetof(rec_hdr, dirbase);
const size_t filename_len = b[22];
const size_t dirname_len = strlen(dirname) + 1;
const size_t rec_size = ((23 + filename_len + 1 + 3) & ~3) +
(2 * overhead) +
((dirname_len + 3 & ~3));
rec_hdr *new_rec;
if (NameCache.data == NULL || rec_size >= cachesize) return;
if ((NameCache.head + rec_size) > cachesize) {
/* Re-use first record as we will require a wrap-around */
rec_hdr *tailp;
NameCache.tail = 0;
while (NameCache.tail < rec_size) {
tailp = (rec_hdr *) (NameCache.data + NameCache.tail);
if (NameCache.tail == NameCache.head) {
/* NameCache_Trim() will sort this out */
break;
}
NameCache.tail += tailp->offset_next;
}
debug2("Tail now %#x ; Head now %#x\n", NameCache.tail, NameCache.head);
if (NameCache.head != NameCache.tail) {
/* If they are equal, NameCache_Trim() will reset the queue */
NameCache.head = 0;
}
}
else if ((NameCache.tail < NameCache.head) || NameCache.last == -1) {
/* OK - we haven't got a loop active */
}
else while ((NameCache.tail - NameCache.head) < rec_size) {
/* Buffer is already wrapped, but we can afford to wrap it */
rec_hdr *tailp = (rec_hdr *) (NameCache.data + NameCache.tail);
debug1("Discarding entry at %#x\n", NameCache.tail);
NameCache.tail += tailp->offset_next;
if (NameCache.tail <= NameCache.head) {
/* Have wrapped around */
break;
}
}
NameCache_Trim();
/* Locate insertion point and add onto queue */
if (NameCache.last != -1) {
rec_hdr *lastp = (rec_hdr *) (NameCache.data + NameCache.last);
lastp->offset_next = NameCache.head - NameCache.last;
}
debug2("Adding `%s' in `%s'\n", (char *)b+23, dirname);
NameCache.last = NameCache.head;
NameCache.head = NameCache.head + rec_size - overhead;
new_rec = (rec_hdr *) (NameCache.data + NameCache.head);
new_rec->offset_data = -1;
new_rec->offset_next = 0;
new_rec = (rec_hdr *) (NameCache.data + NameCache.last);
new_rec->offset_data = overhead + ((dirname_len + 3) & ~3);
new_rec->offset_next = NameCache.head - NameCache.last;
memcpy(new_rec->dirbase, dirname, dirname_len);
memcpy(NameCache.data + NameCache.last + new_rec->offset_data, b,
23 + filename_len);
NameCache.data[NameCache.last + new_rec->offset_data + 23 + filename_len] = '\0';
}
#ifdef TEST
static void DumpBuffer(void *ptr, int len)
{
const char *membuf = ptr;
int i,j;
for (i=0; i<((len+31)&~31); ++i) {
if (!(i & 31)) {
printf(" ");
if (i) for (j = i - 32; j != i; ++j) {
printf("%c", (membuf[j]>=32 && membuf[j] != 0x7f) ?
membuf[j] : '.');
}
printf("\n%04x: ", i);
}
if (i>=len) {
printf(" ");
if (3==(i & 3)) printf(" ");
}
else {
printf("%02x", membuf[i]);
if (3==(i & 3)) printf(" ");
}
}
if (i) for (printf(" "), j = i - 32; j != i; ++j) printf("%c",
j>=len ? ' ' : (membuf[j]>=32 && membuf[j] != 0x7f) ?
membuf[j] : '.');
printf("\n");
}
static void DumpNameCache(void)
{
printf("head = %#x\ntail = %#x\nlast = %#x\nData = %p",
NameCache.head, NameCache.tail, NameCache.last, NameCache.data);
DumpBuffer(NameCache.data, cachesize);
}
static void SoakTest(void)
{
int i, j;
BYTE entry[256], *res;
char dirname[256];
char fullname[256];
NameCache_Init();
/* Force repeatability */
srand(1);
memset(entry, 7, sizeof(entry));
for (i=0;i<500000;++i) {
int dlen = (rand() % 32) + 1;
int llen = (rand() % 64) + 1;
if (!(i % 256)) printf("%8d", i);
for (j=0; j<(dlen+llen); ++j) {
dirname[j] = (rand() % 26) + 'A';
entry[23 + j] = (rand() % 26) + 'a';
}
entry[22] = llen;
dirname[dlen] = '\0';
//printf("Add `%s' `%.*s'\n", dirname, llen, (char *)entry+23);
NameCache_Add(0, dirname, entry);
sprintf(fullname, "%s\\%.*s", dirname, llen, (char *)entry+23);
//printf("Seeking `%s'\n", fullname);
res = NameCache_Locate(fullname, 0);
if (!res) {
DumpNameCache();
printf("\n\n(%d) Failed to find entry!\n", i);
exit(1);
}
}
printf("\n");
}
int main(void)
{
BYTE entry[256], *res;
char fullname[64], *const leafptr = (char *) entry+23;
char *dirname = "A:\\ADIRECTORY";
char *leafname = "filen";
sprintf(fullname, "%s\\%s", dirname, leafname);
res = NameCache_Locate(fullname, 0);
printf("Lookup returned %p (%#08x)\n", res, res - NameCache.data);
memset(entry, 4, sizeof(entry));
entry[22] = strlen(leafname);
strcpy(leafptr, leafname);
NameCache_Init();
DumpNameCache();
NameCache_Add(0, dirname, entry);
dirname = "A:\\2NDDIRNAME";
NameCache_Add(0, dirname, entry);
dirname = "A:\\3RDDIRNAME";
NameCache_Add(0, dirname, entry);
//DumpNameCache();
dirname = "B:\\BDIRNAME";
NameCache_Add(0, dirname, entry);
NameCache_Add(0, dirname, entry);
DumpNameCache();
dirname = "C:\\ANOTHERCDIR";
NameCache_Add(0, dirname, entry);
DumpNameCache();
leafname = "a very long filename generated to cause trouble"\
"as several items should be thrown away and cause a cache reset to occur?";
entry[22] = strlen(leafname);
strcpy(leafptr, leafname);
DumpNameCache();
NameCache_Add(0, dirname, entry);
DumpNameCache();
sprintf(fullname, "%s\\%s", dirname, leafname);
res = NameCache_Locate(fullname, 0);
printf("Lookup returned %p (%#08x)\n", res, res - NameCache.data);
SoakTest();
return 0;
}
#endif /* TEST */
#endif /* LONGNAMES */