NameCache

/* 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;
        debug1("NameCache hits: %d\n", NameCache.hits);
}

void NameCache_Flush(ncf_reason why)
{
        debug1("NameCacheFlush(reason = %d)\n", why);
        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 */