mcache.h

Go to the documentation of this file.

/* -*-  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 caches
// 
// $Header: /nfs/jade/vint/CVSROOT/ns-2/webcache/mcache.h,v 1.6 1999/11/18 23:14:34 haoboy Exp $

#ifndef ns_mcache_h
#define ns_mcache_h

#include "config.h"
#include "agent.h"
#include "pagepool.h"
#include "http.h"
#include "rap/media-app.h"


//----------------------------------------------------------------------
// Priority list for hit counts at each layer
//----------------------------------------------------------------------
class HitCount : public DoubleListElem {
public:
        HitCount(ClientPage *pg, short layer) : 
                DoubleListElem(), pg_(pg), layer_(layer), hc_(0) {}

        void update(float hc) { hc_ += hc; }
        float hc() { return hc_; }
        void reset() { hc_ = 0; }
        ClientPage* page() { return pg_; }
        short layer() { return layer_; }

        HitCount* next() { return (HitCount *)DoubleListElem::next(); }
        HitCount* prev() { return (HitCount *)DoubleListElem::prev(); }

private:
        ClientPage* pg_;        // page
        short layer_;           // layer id
        float hc_;              // hit count
};

class HitCountList : public DoubleList {
public:
        HitCountList() : DoubleList() {}

        void update(HitCount *h);       // Update layer hit count
        void add(HitCount *h);          // Add a new layer

        HitCount* detach_tail() {
                HitCount* tmp = (HitCount *)tail_;
                if (tmp) {
                        tail_ = tail_->prev();
                        tmp->detach();
                }
                return tmp;
        }

        // Debug only
        void print();
        void check_integrity(); 
};



//----------------------------------------------------------------------
// Multimedia web objects
//----------------------------------------------------------------------
class MediaPage : public ClientPage {
public:
        MediaPage(const char *n, int s, double mt, double et, double a, int l);
        virtual ~MediaPage();

        virtual WebPageType type() const { return MEDIA; }
        virtual void print_info(char *buf);
        int num_layer() const { return num_layer_; }

        HitCount* get_hit_count(int layer) { 
                assert((layer >= 0) && (layer < num_layer_));
                return hc_[layer]; 
        }
        void hit_layer(int layer) {
                assert((layer >= 0) && (layer < num_layer_));
                hc_[layer]->update((double)(layer_[layer].length()*num_layer_)
                                   / (double)size_); 
        }

        int layer_size(int layer) { 
                assert((layer >= 0) && (layer < num_layer_));
                return layer_[layer].length();
        }
        void add_segment(int layer, const MediaSegment& s);
        int evict_tail_segment(int layer, int size);

        void add_layer(int layer) {
                assert((layer >= 0) && (layer < num_layer_));
                num_layer_ = (num_layer_ < layer) ? layer : num_layer_;
        }
        char* print_layer(int layer) {
                assert((layer >= 0) && (layer < num_layer_));
                return layer_[layer].dump2buf();
        }
        MediaSegmentList is_available(int layer, const MediaSegment& s) {
                assert((layer >= 0) && (layer < MAX_LAYER));
                return layer_[layer].check_holes(s);
        }
        // Return a media segment which is the closest one after 's'.
        // Used by MediaApps to request data.
        // Do NOT check if layer >= num_layer_. If it's empty, 
        // an empty MediaSegment will be returned. 
        MediaSegment next_available(int layer, const MediaSegment& s) {
                assert((layer >= 0) && (layer < MAX_LAYER));
                return layer_[layer].get_nextseg(s);
        }
        MediaSegment next_overlap(int layer, const MediaSegment& s) {
                assert((layer >= 0) && (layer < MAX_LAYER));
                MediaSegment s1 = layer_[layer].get_nextseg(s);
                if ((s1.end() <= s.start()) || (s1.start() >= s.end())) {
                        MediaSegment s;
                        if (s1.is_last())
                                s.set_last();
                        return s;
                } else
                        return s1;
        }

        enum {FETCHLOCK = 1, XMITLOCK = 2};

        // 1st type of lock: it is being fetched from the server
        void lock() { locked_ |= FETCHLOCK; }
        void unlock() { locked_ &= ~FETCHLOCK; }
        int is_locked() { return (locked_ & FETCHLOCK); }
        // 2nd type of lock: it is being transmitted to a client
        void tlock() { locked_ |= XMITLOCK; }
        void tunlock() { locked_ &= ~XMITLOCK; }
        int is_tlocked() { return (locked_ & XMITLOCK); }

        // Whether all layers are marked as "completed"
        int is_complete(); 
        // Set all layers as "completed"
        void set_complete();

        // Given the number of layers, evenly distribute the size among all
        // layers and create all segments.
        void create();
        int realsize() const { return realsize_; }

protected:
        void set_complete_layer(int layer) {
                flags_[layer] = 1;
        }
        int is_complete_layer(int layer) {
                return flags_[layer] == 1; 
        }

        MediaSegmentList layer_[MAX_LAYER];
        int flags_[MAX_LAYER]; // If 1, marks the layer as completed
        HitCount* hc_[MAX_LAYER];
        int num_layer_; 
        int locked_;  // If 1, then no segment can be replaced
        int realsize_; // The size of stream data in this page.
};

// XXX Later we should add a generic replacement algorithm hook into 
// ClientPagePool. But now we'll leave it there and get this media 
// page pool work first. 

// ClientPagePool enhanced with support for multimedia objects, and 
// with replacement algorithms
class MClientPagePool : public ClientPagePool {
public:
        MClientPagePool();

        virtual ClientPage* enter_page(int argc, const char*const* argv);
        virtual int remove_page(const char *name);
        virtual int force_remove(const char *name);

        int add_segment(const char *name, int layer, const MediaSegment& s);
        void hc_update(const char *name, int max_layer);

        int maxsize() { return max_size_; }
        int usedsize() { return used_size_; }

        void fill_page(const char* pgname);

        // Debug only
        void dump_hclist() { hclist_.print(); }

protected:
        virtual int command(int argc, const char*const* argv);
        virtual int cache_replace(ClientPage* page, int size);

        // Fine-grain replacement
        int repl_finegrain(ClientPage* p, int size);
        int repl_atomic(ClientPage* p, int size);

        // XXX Should change to quad_t, or use MB as unit
        int max_size_;          // PagePool size
        int used_size_;         // Available space size
        HitCountList hclist_; 
        // Replacement style
        enum { FINEGRAIN, ATOMIC } repl_style_;
};

// Provide page data and generate requests for servers and clients
class MediaPagePool : public PagePool {
public:
        MediaPagePool();
protected:
        virtual int command(int argc, const char*const* argv);
        int layer_;     // Number of layers of pages
        int *size_;     // Page sizes
        RandomVariable *rvReq_;
};



//--------------------
// Multimedia caches
//--------------------

// Plain multimedia cache, which can interface with RapAgent
class MediaCache : public HttpCache {
public:
        MediaCache();
        ~MediaCache();

        // Handle app-specific data in C++
        virtual void process_data(int size, AppData* data);
        // Handle data request from RAP
        virtual AppData* get_data(int& size, AppData* data);

protected:
        virtual int command(int argc, const char*const* argv);

        // Do we need to maintain links to MediaApp?? I doubt not
        // MediaApp* mapp_; // An array of incoming/outgoing RAP agents
        MClientPagePool* mpool() { return (MClientPagePool *)pool_; }

        // Information and statistics related to clients
        struct RegInfo {
                RegInfo() : client_(NULL), hl_(-1) {
                        memset(pb_, 0, sizeof(unsigned int)*MAX_LAYER);
                        memset(db_, 0, sizeof(unsigned int)*MAX_LAYER);
                        memset(eb_, 0, sizeof(unsigned int)*MAX_LAYER);
                }
                ~RegInfo() {
                        for (int i = 0; i < MAX_LAYER; i++)
                                pref_[i].destroy();
                }

                char name_[20];
                HttpApp* client_;
                int hl_;                // Highest layer this client has asked
                // Prefetched bytes
                unsigned int pb_[MAX_LAYER]; 
                // Prefetched bytes that were delivered
                unsigned int eb_[MAX_LAYER];
                // Total delivered bytes
                unsigned int db_[MAX_LAYER];
                MediaSegmentList pref_[MAX_LAYER];

                // Return the number of prefetched bytes in the given segment
                void add_pref(int layer, const MediaSegment& s) {
                        assert((layer >= 0) && (layer < MAX_LAYER));
                        pref_[layer].add(s);
                }
                int pref_size(int layer, const MediaSegment &s) const { 
                        assert((layer >= 0) && (layer < MAX_LAYER));
                        return pref_[layer].overlap_size(s);
                }
        };
        Tcl_HashTable *cmap_;   // client map

        // Prefetching/No-prefetching/Offline-prefetching flag
        enum {NOPREF, ONLINE_PREF, OFFLINE_PREF} pref_style_;
};


//----------------------------------------------------------------------
// Multimedia web client
//----------------------------------------------------------------------
class MediaClient : public HttpClient {
public:
        MediaClient() : HttpClient() {}
        virtual void process_data(int size, AppData* data);
        virtual int command(int argc, const char*const* argv);
private:
        MClientPagePool* mpool() { return (MClientPagePool *)pool_; }
};



// Helper data structure

template <class T> class Queue; // forward declaration

template <class T> class QueueElem {
public:
        QueueElem(T* d) : next_(0), data_(d) {}

        QueueElem<T>* next() const { return next_; }
        T* data() const { return data_; }
        void detachData() { data_ = NULL; }
        void append(QueueElem<T>* e) {
                e->next_ = next_;
                next_ = e;
        }

protected:
        QueueElem<T>* next_;
        T* data_;
        friend class Queue<T>; 
};

template <class T> class Queue {
public:
        Queue() : head_(0), tail_(0), size_(0) {}
        virtual ~Queue() {
                QueueElem<T> *p = head_, *q;
                while (p != NULL) {
                        q = p;
                        p = p->next();
                        delete q;
                }
                head_ = NULL;
        }
        virtual void reset() {
                QueueElem<T> *p = head_, *q;
                while (p != NULL) {
                        q = p;
                        p = p->next();
                        delete q;
                }
                head_ = NULL;
        }
        virtual void destroy() {
                QueueElem<T> *p = head_, *q;
                while (p != NULL) {
                        q = p;
                        p = p->next();
                        delete q->data();
                        delete q;
                }
                head_ = NULL;
        }

        void enqueue(QueueElem<T> *e) {
                if (tail_ == 0)
                        head_ = tail_ = e;
                else {
                        tail_->append(e);
                        tail_ = e;
                }
                size_++;
        }
        QueueElem<T>* dequeue() {
                QueueElem<T> *p = head_;
                if (head_ != 0) 
                        head_ = head_->next();
                if (head_ == 0)
                        tail_ = 0;
                p->next_ = 0;
                size_--;
                if (size_ == 0) 
                        assert((head_ == 0) && (tail_ == 0));
                return p;
        }
        void detach(QueueElem<T>* e) {
                assert(head_ != 0);
                if (head_ == e) {
                        dequeue();
                        return;
                }
                QueueElem<T> *p = head_;
                while (p != NULL) {
                        if (p->next_ != e)
                                p = p->next_;
                        else
                                break;
                }
                assert(p != NULL);
                p->next_ = e->next_;
                if (tail_ == e)
                        tail_ = p;
                size_--;
                if (size_ == 0) 
                        assert((head_ == 0) && (tail_ == 0));
        }
        QueueElem<T>* getHead() { return head_; }
        int is_empty() const { return (size_ == 0); }
        int size() const { return size_; }

protected:
        QueueElem<T> *head_, *tail_;
        int size_;
};



//----------------------------------------------------------------------
// Multimedia server
//----------------------------------------------------------------------
class MediaServer : public HttpServer {
public:
        MediaServer();
        ~MediaServer();
        virtual AppData* get_data(int& size, AppData* d);

protected:
        virtual int command(int argc, const char*const* argv);
        MediaSegment get_next_segment(MediaRequest *r, Application*& ci);

        // Prefetching list
        struct RegInfo {
                char name_[20];
                HttpApp* client_;
        };
        struct PrefInfo {
                MediaSegmentList* sl_;
                Application* conid_;
        };
        typedef Queue<PrefInfo> PrefInfoQ;
        typedef QueueElem<PrefInfo> PrefInfoE;
        PrefInfoE* find_prefinfo(PrefInfoQ* q, Application* conid) {
                for (PrefInfoE *e = q->getHead(); e != NULL; e = e->next())
                        if (e->data()->conid_ == conid)
                                return e;
                return NULL;
        }

        Tcl_HashTable *pref_; // Mapping <cache>:<pagenum> to PrefInfoQ
        Tcl_HashTable *cmap_; // Mapping MediaApps to clients

        PrefInfoQ* get_piq(const char* pgname, HttpApp* client) {
                PageID id;
                ClientPage::split_name(pgname, id);
                int tmp[2];
                tmp[0] = (int)(client);
                tmp[1] = id.id_;
                Tcl_HashEntry* he = 
                        Tcl_FindHashEntry(pref_, (const char*)tmp);
                if (he == NULL) 
                        return NULL;
                return (PrefInfoQ*)Tcl_GetHashValue(he);
        }
        RegInfo* get_reginfo(Application* app) {
                Tcl_HashEntry *he = 
                        Tcl_FindHashEntry(cmap_, (const char *)app);
                if (he == NULL) {
                        fprintf(stderr, "Unknown connection!\n");
                        abort();
                } 
                return (RegInfo *)Tcl_GetHashValue(he);
        }
};


#endif // ns_mcache_h

---