mcache.cc

柯老师网站上找到的

/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
//
// Copyright (c) 1997 by the University of Southern California
// All rights reserved.
//
// Permission to use, copy, modify, and distribute this software and its
// documentation in source and binary forms for non-commercial purposes
// and without fee is hereby granted, provided that the above copyright
// notice appear in all copies and that both the copyright notice and
// this permission notice appear in supporting documentation. and that
// any documentation, advertising materials, and other materials related
// to such distribution and use acknowledge that the software was
// developed by the University of Southern California, Information
// Sciences Institute.  The name of the University may not be used to
// endorse or promote products derived from this software without
// specific prior written permission.
//
// THE UNIVERSITY OF SOUTHERN CALIFORNIA makes no representations about
// the suitability of this software for any purpose.  THIS SOFTWARE IS
// PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// Other copyrights might apply to parts of this software and are so
// noted when applicable.
//
// Multimedia cache implementation
//
// $Header: /nfs/jade/vint/CVSROOT/ns-2/webcache/mcache.cc,v 1.11 1999/12/20 19:20:40 haoboy Exp $

#include <assert.h>
#include <stdio.h>

#include "rap/media-app.h"
#include "mcache.h"


MediaPage::MediaPage(const char *n, int s, double mt, double et, 
		     double a, int l) :
	ClientPage(n, s, mt, et, a), num_layer_(l), locked_(0), realsize_(0)
{
	for (int i = 0; i < num_layer_; i++) {
		hc_[i] = new HitCount(this, i);
		flags_[i] = 0;
	}
}

MediaPage::~MediaPage()
{
	int i; 
	for (i = 0; i < num_layer_; i++) {
		// Delete hit count list
		// These hit count records should have already been removed
		// from the cache's hit count list. 
		assert((hc_[i]->prev() == NULL) && (hc_[i]->next() == NULL));
		delete hc_[i];
		// Delete media segment list
		layer_[i].destroy();
	}
}

void MediaPage::print_info(char *buf) 
{
	ClientPage::print_info(buf);
	buf += strlen(buf);
	sprintf(buf, " pgtype MEDIA layer %d", num_layer_);
}

// Make the page full with stream data
void MediaPage::create()
{
	assert((num_layer_ >= 0) && (num_layer_ < MAX_LAYER));
	int i, sz = size_ / num_layer_;
	for (i = 0; i < num_layer_; i++) {
		// Delete whatever that was there. 
		layer_[i].destroy();
		add_segment(i, MediaSegment(0, sz));
		set_complete_layer(i);
	}
	realsize_ = size_;
}

void MediaPage::add_segment(int layer, const MediaSegment& s) 
{
	assert((layer >= 0) && (layer < MAX_LAYER));
	layer_[layer].add(s);
	realsize_ += s.datasize();
	if (s.is_last())
		set_complete_layer(layer);
}

int MediaPage::is_complete()
{
	// Consider a page finished when all NON-EMPTY layers are 
	// marked as "completed"
	for (int i = 0; i < num_layer_; i++)
		if (!is_complete_layer(i) && (layer_[i].length() > 0))
			return 0;
	return 1;
}

void MediaPage::set_complete()
{
	for (int i = 0; i < num_layer_; i++)
		set_complete_layer(i);
}

// Used for cache replacement
int MediaPage::evict_tail_segment(int layer, int size)
{
	if (is_locked() || is_tlocked())
		return 0;

	assert((layer >= 0) && (layer < MAX_LAYER));
	//#ifdef MCACHE_DEBUG
#if 0
	char buf[20];
	name(buf);
	fprintf(stderr, "Page %s evicted layer %d: ", buf, layer);
#endif
	int sz = layer_[layer].evict_tail(size);
	realsize_ -= sz;
	//#ifdef MCACHE_DEBUG
#if 0
	fprintf(stderr, "\n");
#endif
	return sz;
}



//----------------------------------------------------------------------
// Classes related to a multimedia client page pool
//
// HitCountList and MClientPagePool
//----------------------------------------------------------------------

void HitCountList::update(HitCount *h)
{
	HitCount *tmp = h->prev();
	if ((tmp != NULL) && (tmp->hc() < h->hc())) {
		// Hit count increased, need to move this one up
		detach(h);
		while ((tmp != NULL) && (tmp->hc() < h->hc())) {
			if ((tmp->page() == h->page()) &&
			    (tmp->layer() < h->layer()))
				// XXX Don't violate layer encoding within the
				// same page!
				break;
			tmp = tmp->prev();
		}
		if (tmp == NULL) 
			// Insert it at the head
			insert(h, head_);
		else 
			append(h, tmp);
	} else if ((h->next() != NULL) && (h->hc() < h->next()->hc())) {
		// Hit count decreased, need to move this one down
		tmp = h->next();
		detach(h);
		while ((tmp != NULL) && (h->hc() < tmp->hc())) {
			if ((h->page() == tmp->page()) && 
			    (h->layer() < tmp->layer()))
				// XXX Don't violate layer encoding within 
				// the same page!
				break;
			tmp = tmp->next();
		}
		if (tmp == NULL)
			// At the tail
			append(h, tail_);
		else
			insert(h, tmp);
	}
	// We may end up with two cases here:
	//
	// (1) tmp->hc()>h->hc() && tmp->layer()<h->layer(). This is
	// the normal case, where both hit count ordering and layer 
	// ordering are preserved;
	//
	// (2) tmp->hc()>h->hc() && tmp->layer()>h->layer(). In this
	// case, we should move h BEFORE tmp so that the layer 
	// ordering is not violated. We basically order the list using 
	// layer number as primary key, and use hit count as secondary
	// key. 
	// Note that the hit count ordering is only violated when more packets 
	// in layer i are dropped than those in layer i+1.
}

// Check the integrity of the resulting hit count list
void HitCountList::check_integrity()
{
	HitCount *p = (HitCount*)head_, *q;
	while (p != NULL) {
		q = p->next();
		while (q != NULL) {
			// Check layer ordering 
			if ((p->page() == q->page()) && 
			    (p->layer() > q->layer())) {
				fprintf(stderr, "Wrong hit count list.\n");
				abort();
			}
			q = q->next();
		}
		p = p->next();
	}
}

void HitCountList::add(HitCount *h)
{
	HitCount *tmp = (HitCount*)head_;

	// XXX First, ensure that the layer ordering within the same page
	// is not violated!!
	while ((tmp != NULL) && (tmp->hc() > h->hc())) {
		if ((tmp->page() == h->page()) && (tmp->layer() > h->layer()))
			break;
		tmp = tmp->next();
	}
	// Then order according to layer number
	while ((tmp != NULL) && (tmp->hc() == h->hc()) && 
	       (tmp->layer() < h->layer()))
		tmp = tmp->next();

	if (tmp == NULL) {
		if (head_ == NULL) 
			head_ = tail_ = h;
		else
			append(h, tail_);
		return;
	} else if ((tmp == head_) && 
		   ((tmp->hc() < h->hc()) || (tmp->layer() > h->layer()))) {
		insert(h, head_);
		return;
	}

	// Now tmp->hc()<=h->hc(), or tmp->hc()>h->hc() but 
	// tmp->layer()>h->layer(), insert h BEFORE tmp
	insert(h, tmp);
}

// Debug only
void HitCountList::print() 
{
	HitCount *p = (HitCount *)head_;
	int i = 0;
	char buf[20];
	while (p != NULL) {
		p->page()->name(buf);
	        fprintf(stderr, "(%s %d %f) ", buf, p->layer(), p->hc());
		if (++i % 4 == 0)
			printf("\n");
		p = p->next();
	}
	if (i % 4 != 0)
		fprintf(stderr, "\n");
}

//------------------------------
// Multimedia client page pool
//------------------------------
static class MClientPagePoolClass : public TclClass {
public:
        MClientPagePoolClass() : TclClass("PagePool/Client/Media") {}
        TclObject* create(int, const char*const*) {
		return (new MClientPagePool());
	}
} class_mclientpagepool_agent;

MClientPagePool::MClientPagePool() : 
	used_size_(0), repl_style_(FINEGRAIN)
{
	bind("max_size_", &max_size_);
	used_size_ = 0;
}

int MClientPagePool::command(int argc, const char*const* argv)
{
	if (argc == 3) 
		if (strcmp(argv[1], "set-repl-style") == 0) {
			// Set replacement style
			// <obj> set-repl-style <style>
			if (strcmp(argv[2], "FINEGRAIN") == 0) 
				repl_style_ = FINEGRAIN;
			else if (strcmp(argv[2], "ATOMIC") == 0)
				repl_style_ = ATOMIC;
			else {
				fprintf(stderr, "Unknown style %s", argv[3]);
				return (TCL_ERROR);
			}
			return (TCL_OK);
		}
	return ClientPagePool::command(argc, argv);
}

void MClientPagePool::hc_update(const char *name, int max_layer)
{
	MediaPage *pg = (MediaPage*)get_page(name);
	assert(pg != NULL);

	int i;
	HitCount *h;
	// First we update the hit count of each layer of the given page
	for (i = 0; i <= max_layer; i++)
		pg->hit_layer(i);
	// Then we update the position of these hit count records
	for (i = 0; i <= max_layer; i++) {
		h = pg->get_hit_count(i);
		hclist_.update(h);
	}
#if 1
	hclist_.check_integrity();
#endif
}

// Add a segment to an object, and adjust hit counts accordingly
// XXX Call cache replacement algorithm if necessary
int MClientPagePool::add_segment(const char* name, int layer, 
				 const MediaSegment& s)
{
	MediaPage* pg = (MediaPage *)get_page(name);
	if (pg == NULL)
		return -1;
	if (layer >= pg->num_layer()) {
		if (s.datasize() == 0)
			return 0;
		else {
			fprintf(stderr, 
				"MClientPagePool: cannot add a new layer.\n");
			abort();
		}
	}

	// Check space availability
	if (used_size_ + s.datasize() > max_size_) {
		// If atomic replacement is used, page size is deducted in
		// remove_page(). If fine-grain is used, evicted size is 
		// deducted in repl_finegrain().
		cache_replace(pg, s.datasize());
		//#ifdef MCACHE_DEBUG
#if 0
		fprintf(stderr, 
			"Replaced for page %s segment (%d %d) layer %d\n",
			name, s.start(), s.end(), layer);
#endif
	} 
	// Add new page. When we are doing atomic replacement, the size that
	// we evicted may be larger than what we add.
	used_size_ += s.datasize();

	// If this layer was not 'in' before, add its hit count block
	if (pg->layer_size(layer) == 0)
		hclist_.add(pg->get_hit_count(layer));

	// Add new segment
	pg->add_segment(layer, s);

	return 0;
}

void MClientPagePool::fill_page(const char* pgname)
{
	MediaPage *pg = (MediaPage*)get_page(pgname);
	used_size_ -= pg->realsize();
	// Lock this page before we do any replacement. 
	pg->lock();
	pg->create();
	// If we cannot hold the nominal size of the page, do replacement
	if (used_size_ + pg->size() > max_size_)
		// Size deduction has already been done in remove_page()
		cache_replace(pg, pg->size());
	used_size_ += pg->size();
	pg->unlock();
}

ClientPage* MClientPagePool::enter_page(int argc, const char*const* argv)
{
	double mt = -1, et, age = -1, noc = 0;
	int size = -1, media_page = 0, layer = -1;
	for (int i = 3; i < argc; i+=2) {
		if (strcmp(argv[i], "modtime") == 0)
			mt = strtod(argv[i+1], NULL);
		else if (strcmp(argv[i], "size") == 0) 
			size = atoi(argv[i+1]);
		else if (strcmp(argv[i], "age") == 0)
			age = strtod(argv[i+1], NULL);
		else if (strcmp(argv[i], "noc") == 0)
			// non-cacheable flag
			noc = 1;
		else if (strcmp(argv[i], "pgtype") == 0) {
			if (strcmp(argv[i+1], "MEDIA") == 0)
				media_page = 1;
		} else if (strcmp(argv[i], "layer") == 0)
			layer = atoi(argv[i+1]);
	}
	// XXX allow mod time < 0 and age < 0!
	if ((size < 0) || (media_page && (layer <= 0))) {
		fprintf(stderr, "%s: wrong page information %s\n",
			name_, argv[2]);
		return NULL;
	}
	et = Scheduler::instance().clock();
	ClientPage *pg;
	if (media_page)
		pg = new MediaPage(argv[2], size, mt, et, age, layer);
	else 
		pg = new ClientPage(argv[2], size, mt, et, age);
	if (add_page(pg) < 0) {
		delete pg;
		return NULL;
	}
	if (noc) 
		pg->set_uncacheable();
	if (media_page) 
		((MediaPage *)pg)->lock();
	return pg;
}

int MClientPagePool::cache_replace(ClientPage *pg, int size)
{
	switch (repl_style_) {
	case FINEGRAIN:
		return repl_finegrain(pg, size);
	case ATOMIC:
#if 0
		char tmp[128];
		pg->name(tmp);
		fprintf(stderr, "Replaced for page %s size %d\n", tmp, size);
		fprintf(stderr, "Used size %d, max size %d\n", used_size_, 
			max_size_);
#endif
		return repl_atomic(pg, size);
	default:
		fprintf(stderr, "Corrupted replacement style.\n");
		abort();
	}
	// To make msvc happy
	return -1;
}

int MClientPagePool::repl_atomic(ClientPage*, int size)
{
	// XXX We use standard LRU to determine the stream to be kicked out.
	// The major problem is that we do not keep discrete hit counts. 
	// We solve the problem by using hit counts of the base layer as 
	// a close approximate. Because whenever a stream is accessed, 
	// it's assumed that the client bw can always afford the base layer,
	// this should be a fairly good approximation. 

	HitCount *h, *p;
	int sz, totalsz = 0;
	// Repeatedly get rid of streams until get enough space
	h = (HitCount*)hclist_.tail();
	while (h != NULL) {
		if (h->layer() != 0) {
			// We only look for the base layer
			h = h->prev();
			continue;
		}
		MediaPage *pg = (MediaPage *)h->page();
		// Don't touch locked pages
		if (pg->is_tlocked() || pg->is_locked()) {
			h = h->prev();
			continue;
		}
		sz = pg->realsize();
		totalsz += sz;
		char tmp[HTTP_MAXURLLEN];
		pg->name(tmp);
		// Before we delete, find the previous hit count record that
		// does not belong to this page. 
		p = h->prev(); 
		while ((p != NULL) && (p->page() == h->page()))
			p = p->prev();
		h = p;
		// XXX Manually remove hit count before deleting it
		for (int i = 0; i < pg->num_layer(); i++) {
			p = pg->get_hit_count(i);
			hclist_.detach(p);
		}
		// Delete the page, together with its media segment list
#if 0
		fprintf(stderr, "At time %g, atomic replacement evicted page %s\n", 
			Scheduler::instance().clock(), tmp); 
		fprintf(stderr, "Hit count list: \n");
		hclist_.print();
		fprintf(stderr,"----------------------------------------\n\n");
#endif		
		remove_page(tmp);
		if (sz >= size)
			return totalsz;
		// Continue to evict to meet the space requirement
		size -= sz;
	}
	fprintf(stderr, "Cache replacement cannot get enough space.\n");