packetbatch.hh

// -*- related-file-name: "../../lib/packetbatch.cc" -*-
#ifndef CLICK_PACKETBATCH_HH
#define CLICK_PACKETBATCH_HH
 
#include <click/packet.hh>
CLICK_DECLS
 
#define FOR_EACH_PACKET_LL(first,p) for(Packet* p = first;p != 0;p=p->next())
 
#define FOR_EACH_PACKET(batch,p) FOR_EACH_PACKET_LL(batch->first(),p)
 
#define FOR_EACH_PACKET_LL_SAFE(first,p) \
                Packet* fep_next = ((first != 0)? first->next() : 0 );\
                Packet* p = first;\
                for (;p != 0;p=fep_next,fep_next=(p==0?0:p->next()))
 
 
#define FOR_EACH_PACKET_SAFE(batch,p) FOR_EACH_PACKET_LL_SAFE(batch->first(),p)
 
#define EXECUTE_FOR_EACH_PACKET(fnt,batch) \
                Packet* efep_next = ((batch != 0)? batch->first()->next() : 0 );\
                Packet* p = batch->first();\
                Packet* last = 0;\
                for (;p != 0;p=efep_next,efep_next=(p==0?0:p->next())) {\
                    Packet* q = fnt(p);\
                    if (q != p) {\
                        if (last) {\
                            last->set_next(q);\
                        } else {\
                            batch = reinterpret_cast<PacketBatch*>(q);\
                        }\
                        q->set_next(efep_next);\
                    }\
                    last = q;\
                }
 
#define EXECUTE_FOR_EACH_PACKET_UNTIL_DO(fnt,batch,on_stop) \
                Packet* efep_next = ((batch != 0)? batch->first()->next() : 0 );\
                Packet* p = batch->first();\
                Packet* last = 0;\
                int count = batch->count();\
                for (;p != 0;p=efep_next,efep_next=(p==0?0:p->next())) {\
                    Packet* q = p;\
                    bool drop = !fnt(q);\
                    if (q != p) {\
                        if (last) {\
                            last->set_next(q);\
                        } else {\
                            batch = reinterpret_cast<PacketBatch*>(q);\
                            batch->set_count(count);\
                        }\
                        q->set_next(efep_next);\
                    }\
                    if (unlikely(drop)) {\
                        on_stop(batch, q, efep_next);\
                        break;\
                    }\
                    last = q;\
                }
 
//Variant that will drop the whole batch when fnt return false
#define EXECUTE_FOR_EACH_PACKET_UNTIL(fnt,batch) \
    EXECUTE_FOR_EACH_PACKET_UNTIL_DO(fnt, batch, [](PacketBatch*& batch, Packet*, Packet*){batch->kill();batch = 0;})
 
/*
 * Variant that will drop the remaining packets, but return the batch up to the drop (the packet for which fnt returned true is included.
 * A usage example is a NAT, that translate all packets up to when the state is destroyed. But sometimes there could be unordered packets still coming after the last ACK, or duplicate FIN.
 */
#define EXECUTE_FOR_EACH_PACKET_UNTIL_DROP(fnt,batch) \
    EXECUTE_FOR_EACH_PACKET_UNTIL_DO(fnt, batch, [](PacketBatch*& batch, Packet* dropped, Packet* next){ if (!next) return; PacketBatch* remain = PacketBatch::make_from_simple_list(next);batch->set_count(batch->count() - remain->count()); batch->set_tail(dropped); dropped->set_next(0); remain->kill(); })
 
#define EXECUTE_FOR_EACH_PACKET_DROPPABLE(fnt,batch,on_drop) {\
                Packet* efepd_next = ((batch != 0)? batch->first()->next() : 0 );\
                Packet* p = batch->first();\
                Packet* last = 0;\
                int count = batch->count();\
                for (;p != 0;p=efepd_next,efepd_next=(p==0?0:p->next())) {\
            Packet* q = fnt(p);\
            if (q == 0) {\
                on_drop(p);\
                if (last) {\
                    last->set_next(efepd_next);\
                } else {\
                    batch = PacketBatch::start_head(efepd_next);\
                }\
                        count--;\
                        continue;\
            } else if (q != p) {\
                        if (last) {\
                            last->set_next(q);\
                        } else {\
                            batch = reinterpret_cast<PacketBatch*>(q);\
                        }\
                        q->set_next(efepd_next);\
                    }\
                    last = q;\
                }\
                if (batch) {\
                    batch->set_count(count);\
                    batch->set_tail(last);\
                    last->set_next(0);\
                }\
            }\
 
#define EXECUTE_FOR_EACH_PACKET_DROP_LIST(fnt,batch,drop_list) \
        PacketBatch* drop_list = 0;\
        auto on_drop = [&drop_list](Packet* p) {\
            if (drop_list == 0) {\
                drop_list = PacketBatch::make_from_packet(p);\
            } else {\
                drop_list->append_packet(p);\
            }\
        };\
        EXECUTE_FOR_EACH_PACKET_DROPPABLE(fnt,batch,on_drop);
 
 
#define EXECUTE_FOR_EACH_PACKET_SPLITTABLE(fnt,batch,on_drop,on_flush) {\
            Packet* next = ((batch != 0)? batch->first()->next() : 0 );\
            Packet* p = batch->first();\
            Packet* last = 0;\
            int count = 0;\
            for (;p != 0;p=next,next=(p==0?0:p->next())) {\
                Packet* q = (fnt(p));\
                if (q == 0) {\
                    if (last) {\
                        batch->set_count(count);\
                        batch->set_tail(last);\
                        on_flush(batch);\
                    }\
                    on_drop(p);\
                    count = 0;\
                    last = 0;\
                    batch = PacketBatch::start_head(next);\
                    continue;\
                } else if (q != p) {\
                    if (last) {\
                        last->set_next(q);\
                    } else {\
                        batch = reinterpret_cast<PacketBatch*>(q);\
                    }\
                    q->set_next(next);\
                }\
                last = q;\
                count++;\
            }\
            if (last) {\
                batch->set_count(count);\
                batch->set_tail(last);\
                on_flush(batch);\
            }\
        }\
 
 
#define EXECUTE_FOR_EACH_PACKET_ADD(fnt,batch) {\
            Packet* next = ((batch != 0)? batch->first()->next() : 0 );\
            Packet* p = batch->first();\
            Packet* last = 0;\
            int count = 0;\
            for (;p != 0;p=next,next=(p==0?0:p->next())) {\
                auto add = [&batch,&last,&count](Packet*q) {\
                    if (last) { \
                        last->set_next(q); \
                    } else { \
                        batch = reinterpret_cast<PacketBatch*>(q);\
                    }\
                    last = q;\
                    count++;\
                };\
                fnt(p,add);\
            }\
            if (likely(last)) {\
                batch->set_count(count);\
                batch->set_tail(last);\
                last->set_next(0);\
            } else {\
                batch = 0;\
            }\
        }\
 
#define CLASSIFY_EACH_PACKET(nbatches,fnt,cep_batch,on_finish)\
    {\
        PacketBatch* out[(nbatches)];\
        bzero(out,sizeof(PacketBatch*)*(nbatches));\
        PacketBatch* cep_next = ((cep_batch != 0)? reinterpret_cast<PacketBatch*>(cep_batch->first()->next()) : 0 );\
        Packet* p = cep_batch->first();\
        Packet* last = 0;\
        int last_o = -1;\
        int passed = 0;\
        for (;p != 0;p=cep_next->first(),cep_next=(p==0?0:reinterpret_cast<PacketBatch*>(p->next()))) {\
            int o = (fnt(p));\
            if (o < 0 || o>=(int)(nbatches)) o = (nbatches - 1);\
            if (o == last_o) {\
                passed ++;\
            } else {\
                if (last == 0) {\
                    out[o] = reinterpret_cast<PacketBatch*>(p);\
                    reinterpret_cast<PacketBatch*>(p)->set_count(1);\
                    reinterpret_cast<PacketBatch*>(p)->set_tail(p);\
                } else {\
                    out[last_o]->set_tail(last);\
                    out[last_o]->set_count(out[last_o]->count() + passed);\
                    if (!out[o]) {\
                        out[o] = reinterpret_cast<PacketBatch*>(p);\
                        out[o]->set_count(1);\
                        out[o]->set_tail(p);\
                    } else {\
                        out[o]->append_packet(p);\
                    }\
                    passed = 0;\
                }\
            }\
            last = p;\
            last_o = o;\
        }\
\
        if (passed) {\
            out[last_o]->set_tail(last);\
            out[last_o]->set_count(out[last_o]->count() + passed);\
        }\
\
        unsigned i = 0;\
        for (; i < (unsigned)(nbatches); i++) {\
            if (out[i]) {\
                out[i]->tail()->set_next(0);\
                (on_finish(i,out[i]));\
            }\
        }\
    }
 
#define CLASSIFY_EACH_PACKET_IGNORE(nbatches,fnt,cep_batch,on_finish)\
    {\
        PacketBatch* out[(nbatches)];\
        bzero(out,sizeof(PacketBatch*)*(nbatches));\
        PacketBatch* cep_next = ((cep_batch != 0)? reinterpret_cast<PacketBatch*>(cep_batch->first()->next()) : 0 );\
        Packet* p = cep_batch->first();\
        Packet* last = 0;\
        int last_o = -1;\
        int passed = 0;\
        for (;p != 0;p=cep_next->first(),cep_next=(p==0?0:reinterpret_cast<PacketBatch*>(p->next()))) {\
            int o = (fnt(p));\
            if (o>=(nbatches)) o = (nbatches - 1);\
            if (o == last_o) {\
                passed ++;\
            } else {\
                if (last == 0) {\
                    if (o == -1) continue;\
                    out[o] = reinterpret_cast<PacketBatch*>(p);\
                    out[o]->set_count(1);\
                    out[o]->set_tail(p);\
                } else {\
                    if (last_o != -1) {\
                        out[last_o]->set_tail(last);\
                        out[last_o]->set_count(out[last_o]->count() + passed);\
                    }\
                    if (o != -1) {\
                        if (!out[o]) {\
                            out[o] = reinterpret_cast<PacketBatch*>(p);\
                            out[o]->set_count(1);\
                            out[o]->set_tail(p);\
                        } else {\
                            out[o]->append_packet(p);\
                        }\
                    }\
                    passed = 0;\
                }\
            }\
            last = p;\
            last_o = o;\
        }\
\
        if (passed && last_o != -1) {\
            out[last_o]->set_tail(last);\
            out[last_o]->set_count(out[last_o]->count() + passed);\
        }\
\
        int i = 0;\
        for (; i < (nbatches); i++) {\
            if (out[i]) {\
                out[i]->tail()->set_next(0);\
                (on_finish(i,out[i]));\
            }\
        }\
    }
 
 
#define MAKE_BATCH(fnt,head,max) {\
        head = PacketBatch::start_head(fnt);\
        if (head != 0) {\
            Packet* last = head->first();\
            unsigned int count = 1;\
            while (count < (unsigned)(max>0?max:BATCH_MAX_PULL)) {\
                Packet* current = fnt;\
                if (current == 0)\
                    break;\
                last->set_next(current);\
                last = current;\
                count++;\
            }\
            head->make_tail(last,count);\
        }\
}
 
class PacketBatch {
 
//Consider a batch size bigger as bogus (prevent infinite loop on bad pointer manipulation)
#define MAX_BATCH_SIZE 8192
 
public :
    /*
     * Return the first packet of the batch
     */
    inline Packet* first() {
        return (Packet*)this;
    }
 
    /*
     * Set the tail of the batch
     */
    inline void set_tail(Packet* p) {
        first()->set_prev(p);
    }
 
    /*
     * Return the tail of the batch
     */
    inline Packet* tail() {
        return first()->prev();
    }
    
    /*
     * Append a simply-linked list of packet to the batch.
     * One must therefore pass the tail and the number of packets to do it in constant time. Chances are you
     * just created that list and can track taht.
     */
    inline void append_simple_list(Packet* lhead, Packet* ltail, int lcount) {
        tail()->set_next(lhead);
        set_tail(ltail);
        ltail->set_next(0);
        set_count(count() + lcount);
    }
 
    /*
     * Append a proper PacketBatch to this batch.
     */
    inline void append_batch(PacketBatch* head) {
        tail()->set_next(head->first());
        set_tail(head->tail());
        set_count(count() + head->count());
    }
 
    /*
     * Append a packet to the list.
     */
    inline void append_packet(Packet* p) {
        tail()->set_next(p);
        set_tail(p);
        set_count(count() + 1);
    }
 
    inline unsigned count() {
        unsigned int r = BATCH_COUNT_ANNO(first());
        assert(r); //If this is a batch, this anno has to be set
        return r;
    }
 
    inline static PacketBatch* start_head(Packet* p) {
        return reinterpret_cast<PacketBatch*>(p);
    }
 
    inline PacketBatch* make_tail(Packet* last, unsigned int count) {
        set_count(count);
        if (last == 0) {
            if (count != 1)
                click_chatter("BUG in make_tail : last packet is the head, but count is %u",count);
            set_tail(first());
            first()->set_next(0);
        } else {
            set_tail(last);
            last->set_next(0);
        }
        return this;
    }
 
    inline void set_count(unsigned int c) {
        SET_BATCH_COUNT_ANNO(first(),c);
    }
 
    inline void cut(Packet* middle, int first_batch_count, PacketBatch* &second) {
        if (middle == 0) {
            second = 0;
            click_chatter("BUG Warning : cutting a batch without a location to cut !");
            return;
        }
 
        if (middle == tail()) {
            second = 0;
            return;
        }
 
        int total_count = count();
 
        second = reinterpret_cast<PacketBatch*>(middle->next());
        middle->set_next(0);
 
        Packet* second_tail = tail();
        set_tail(middle);
 
        second->set_tail(second_tail);
        second->set_count(total_count - first_batch_count);
 
        set_count(first_batch_count);
    }
 
    inline void split(int first_batch_count, PacketBatch* &second, const bool &safe = false) {
        Packet* middle = first();
        if (unlikely(!safe)) {
            assert(first_batch_count > 0);
        }
        for (int i = 0; i < first_batch_count - 1; i++) {
            middle = middle->next();
            if (unlikely(!safe && middle == 0)) {
                second = 0;
                break;
            }
        }
 
        int total_count = count();
 
        second = reinterpret_cast<PacketBatch*>(middle->next());
        middle->set_next(0);
 
        Packet* second_tail = tail();
        set_tail(middle);
 
        second->set_tail(second_tail);
        second->set_count(total_count - first_batch_count);
 
        set_count(first_batch_count);
    }
 
    inline PacketBatch* split(int first_batch_count) {
                PacketBatch* second;
                split(first_batch_count,second, false);
                return second;
    }
 
    PacketBatch* pop_front() {
        if (count() == 1)
            return 0;
        PacketBatch* poped = PacketBatch::start_head(first()->next());
        poped->set_count(count() -1 );
        poped->set_tail(tail());
        return poped;
    }
 
    inline static PacketBatch* make_from_tailed_list(Packet* head, unsigned int size) {
        PacketBatch* b = reinterpret_cast<PacketBatch*>(head);
        b->set_count(size);
        return b;
    }
 
    inline static PacketBatch* make_from_simple_list(Packet* head, Packet* tail, unsigned int size) {
        PacketBatch* b = make_from_tailed_list(head,size);
        b->set_tail(tail);
        tail->set_next(0);
        return b;
    }
 
    inline static PacketBatch* make_from_simple_list(Packet* head) {
        int size = 1;
        Packet* next = head->next();
        Packet* tail = head;
        while (next != 0) {
            size++;
            tail = next;
            next = tail->next();
        }
        PacketBatch* b = make_from_tailed_list(head,size);
        b->set_tail(tail);
        return b;
    }
 
 
 
    inline static PacketBatch* make_from_packet(Packet* p) {
        if (!p) return 0;
        PacketBatch* b = reinterpret_cast<PacketBatch*>(p);
        b->set_count(1);
        b->set_tail(p);
        p->set_next(0);
        return b;
    }
 
#if !CLICK_LINUXMODULE
    static PacketBatch *make_batch(unsigned char *data, uint16_t count, uint16_t *length,
                    Packet::buffer_destructor_type destructor,
                                    void* argument = (void*) 0, const bool clear=true) CLICK_WARN_UNUSED_RESULT;
#endif
 
    inline Packet* begin() {
        return first();
    }
 
    inline Packet* end() {
        return tail();
    }
 
    inline void kill();
 
    inline PacketBatch* clone_batch(const bool duplicate = false, const bool duplicate_data_only = false) {
        PacketBatch* head = 0;
        Packet* last = 0;
        FOR_EACH_PACKET(this, p) {
            Packet* q;
            if (duplicate)
                q = p->duplicate(0, 0, duplicate_data_only);
            else
                q = p->clone();
            if (last == 0) {
                head = start_head(q);
                last = q;
            } else {
                last->set_next(q);
                last = q;
            }
        }
        return head->make_tail(last,count());
    }
 
#if HAVE_BATCH && HAVE_CLICK_PACKET_POOL
    void recycle_batch(bool is_data);
 
    void fast_kill();
    void fast_kill_nonatomic();
#else
    inline void fast_kill() {
        kill();
    }
 
    void fast_kill_nonatomic() {
        kill();
    }
#endif
};
 
inline void PacketBatch::kill() {
    FOR_EACH_PACKET_SAFE(this,p) {
        p->kill();
    }
}
 
#if HAVE_BATCH_RECYCLE
#define BATCH_RECYCLE_START() \
        WritablePacket* head_packet = 0;\
        WritablePacket* head_data = 0;\
        WritablePacket* last_packet = 0;\
        WritablePacket* last_data = 0;\
        unsigned int n_packet = 0;\
        unsigned int n_data = 0;
 
#define BATCH_RECYCLE_ADD_PACKET(p) {\
        if (head_packet == 0) {\
                head_packet = static_cast<WritablePacket*>(p);\
                last_packet = static_cast<WritablePacket*>(p);\
        } else {\
                last_packet->set_next(p);\
                last_packet = static_cast<WritablePacket*>(p);\
        }\
        n_packet++;}
 
#define BATCH_RECYCLE_ADD_DATA_PACKET(p) {\
        if (head_data == 0) {\
                head_data = static_cast<WritablePacket*>(p);\
                last_data = static_cast<WritablePacket*>(p);\
        } else {\
                last_data->set_next(p);\
                last_data = static_cast<WritablePacket*>(p);\
        }\
        n_data++;}
 
#define BATCH_RECYCLE_PACKET(p) {\
                        if (p->shared()) {\
                                p->kill();\
                        } else {\
                                BATCH_RECYCLE_UNKNOWN_PACKET(p);\
                        }\
                }
 
#define BATCH_RECYCLE_PACKET_NONATOMIC(p) {\
            if (p->shared_nonatomic()) {\
                p->kill_nonatomic();\
            } else {\
                BATCH_RECYCLE_UNKNOWN_PACKET(p);\
            }\
        }
 
#if HAVE_DPDK_PACKET_POOL
#define BATCH_RECYCLE_UNKNOWN_PACKET(p) {\
        if (p->data_packet() == 0 && (DPDKDevice::is_dpdk_packet(p)) && p->buffer() != 0) {\
                BATCH_RECYCLE_ADD_DATA_PACKET(p);\
        } else {\
                BATCH_RECYCLE_ADD_PACKET(p);}}
#elif !defined(CLICK_NOINDIRECT)
#define BATCH_RECYCLE_UNKNOWN_PACKET(p) {\
        if (p->data_packet() == 0 && p->buffer_destructor() == 0 && p->buffer() != 0) {\
                BATCH_RECYCLE_ADD_DATA_PACKET(p);\
        } else {\
            BATCH_RECYCLE_ADD_PACKET(p);}}
#else
#define BATCH_RECYCLE_UNKNOWN_PACKET(p) {\
        if (p->buffer_destructor() == 0 && p->buffer() != 0) {\
                BATCH_RECYCLE_ADD_DATA_PACKET(p);\
        } else {\
            BATCH_RECYCLE_ADD_PACKET(p);}}
#endif
 
#define BATCH_RECYCLE_END() \
        if (last_packet) {\
                last_packet->set_next(0);\
                PacketBatch::make_from_simple_list(head_packet,last_packet,n_packet)->recycle_batch(false);\
        }\
        if (last_data) {\
                last_data->set_next(0);\
                PacketBatch::make_from_simple_list(head_data,last_data,n_data)->recycle_batch(true);\
        }
#else
#define BATCH_RECYCLE_START() {}
#define BATCH_RECYCLE_END() {}
#define BATCH_RECYCLE_PACKET(p) {p->kill();}
#define BATCH_RECYCLE_PACKET_NONATOMIC(p) {p->kill_nonatomic();}
#endif
 
#define BATCH_RECYCLE_PACKET_CONTEXT(p) {\
            if (likely(is_fullpush())) {\
                BATCH_RECYCLE_PACKET_NONATOMIC(p);\
            } else {\
                BATCH_RECYCLE_PACKET(p);\
            }\
        }
 
#define BATCH_CREATE_INIT(batch) \
        PacketBatch* batch = 0; \
        int batch ## count = 0; \
        Packet* batch ## last = 0;
#define BATCH_CREATE_APPEND(batch,p) \
        if (batch) { \
            batch ## last->set_next(p); \
        } else {\
            batch = PacketBatch::start_head(p); \
        }\
        batch ## last = p;\
        batch ## count++;
#define BATCH_CREATE_FINISH(batch) \
        if (batch) \
            batch->make_tail(batch ## last, batch ## count)
 
typedef Packet::PacketType PacketType;
 
#if HAVE_BATCH && HAVE_CLICK_PACKET_POOL
inline void PacketBatch::recycle_batch(bool is_data) {
    if (is_data) {
        WritablePacket::recycle_data_batch((WritablePacket*)this->first(),tail(),count());
    } else {
        WritablePacket::recycle_packet_batch((WritablePacket*)this->first(),tail(),count());
    }
}
#endif
 
CLICK_ENDDECLS
#endif