lkml.org 
[lkml]   [2005]   [May]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    Subject[patch 17/21] CKRM: Rule Based Classification Engine, bitvector support for classification info
    From
    --
    Content-Disposition: inline; filename=09-03-rbce_main-opt


    Part 3 of 5 patches to support Rule Based Classification Engine for CKRM.
    This patch provides some optimization by maintaining the classification
    information in the vectors. No classification functionality yet.

    Signed-Off-By: Hubertus Franke <frankeh@us.ibm.com>
    Signed-Off-By: Chandra Seetharaman <sekharan@us.ibm.com>
    Signed-Off-By: Shailabh Nagar <nagar@us.ibm.com>
    Signed-Off-By: Vivek Kashyap <vivk@us.ibm.com>
    Signed-Off-By: Gerrit Huizenga <gh@us.ibm.com>

    rbce_bitvector.h | 146 +++++++++++++++++++++++++++++++++++++++++++++++
    rbce_internal.h | 19 +++++-
    rbce_main.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
    3 files changed, 330 insertions(+), 3 deletions(-)

    Index: linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_bitvector.h
    ===================================================================
    --- /dev/null 1970-01-01 00:00:00.000000000 +0000
    +++ linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_bitvector.h 2005-05-05 09:38:05.000000000 -0700
    @@ -0,0 +1,146 @@
    +/*
    + * Copyright (C) Hubertus Franke, IBM Corp. 2003
    + *
    + * Bitvector package
    + *
    + * Latest version, more details at http://ckrm.sf.net
    + *
    + * This program is free software; you can redistribute it and/or modify
    + * it under the terms of the GNU General Public License as published by
    + * the Free Software Foundation; either version 2 of the License, or
    + * (at your option) any later version.
    + *
    + */
    +
    +#ifndef _RBCE_BITVECTOR_H
    +#define _RBCE_BITVECTOR_H
    +
    +typedef struct {
    + int size; /* maxsize in longs */
    + unsigned long bits[0]; /* bit vector */
    +} bitvector_t;
    +
    +#define BITS_2_LONGS(sz) (((sz)+BITS_PER_LONG-1)/BITS_PER_LONG)
    +#define BITS_2_BYTES(sz) (((sz)+7)/8)
    +
    +#if 0
    +#define CHECK_VEC(vec) (vec) /* check against NULL */
    +#else
    +#define CHECK_VEC(vec) (1) /* assume no problem */
    +#endif
    +
    +#define CHECK_VEC_VOID(vec) do { if (!CHECK_VEC(vec)) return; } while(0)
    +#define CHECK_VEC_RC(vec, val) \
    +do { if (!CHECK_VEC(vec)) return (val); } while(0)
    +
    +inline static void bitvector_zero(bitvector_t * bitvec)
    +{
    + int sz;
    +
    + CHECK_VEC_VOID(bitvec);
    + sz = BITS_2_BYTES(bitvec->size);
    + memset(bitvec->bits, 0, sz);
    + return;
    +}
    +
    +inline static unsigned long bitvector_bytes(unsigned long size)
    +{
    + return sizeof(bitvector_t) + BITS_2_BYTES(size);
    +}
    +
    +inline static void bitvector_init(bitvector_t * bitvec, unsigned long size)
    +{
    + bitvec->size = size;
    + bitvector_zero(bitvec);
    + return;
    +}
    +
    +inline static bitvector_t *bitvector_alloc(unsigned long size)
    +{
    + bitvector_t *vec =
    + (bitvector_t *) kmalloc(bitvector_bytes(size), GFP_KERNEL);
    + if (vec) {
    + vec->size = size;
    + bitvector_zero(vec);
    + }
    + return vec;
    +}
    +
    +inline static void bitvector_free(bitvector_t * bitvec)
    +{
    + CHECK_VEC_VOID(bitvec);
    + kfree(bitvec);
    + return;
    +}
    +
    +#define def_bitvec_op(name,mod1,op,mod2) \
    +inline static int name(bitvector_t *res, bitvector_t *op1, \
    + bitvector_t *op2) \
    +{ \
    + unsigned int i, size; \
    + \
    + CHECK_VEC_RC(res, 0); \
    + CHECK_VEC_RC(op1, 0); \
    + CHECK_VEC_RC(op2, 0); \
    + size = res->size; \
    + if (((size != (op1)->size) || (size != (op2)->size))) { \
    + return 0; \
    + } \
    + size = BITS_2_LONGS(size); \
    + for (i = 0; i < size; i++) { \
    + (res)->bits[i] = (mod1 (op1)->bits[i]) op \
    + (mod2 (op2)->bits[i]); \
    + } \
    + return 1; \
    +}
    +
    +def_bitvec_op(bitvector_or,, |,);
    +def_bitvec_op(bitvector_and,, &,);
    +def_bitvec_op(bitvector_xor,, ^,);
    +def_bitvec_op(bitvector_or_not,, |, ~);
    +def_bitvec_op(bitvector_not_or, ~, |,);
    +def_bitvec_op(bitvector_and_not,, &, ~);
    +def_bitvec_op(bitvector_not_and, ~, &,);
    +
    +inline static void bitvector_set(int idx, bitvector_t * vec)
    +{
    + set_bit(idx, vec->bits);
    + return;
    +}
    +
    +inline static void bitvector_clear(int idx, bitvector_t * vec)
    +{
    + clear_bit(idx, vec->bits);
    + return;
    +}
    +
    +inline static int bitvector_test(int idx, bitvector_t * vec)
    +{
    + return test_bit(idx, vec->bits);
    +}
    +
    +#ifdef DEBUG
    +inline static void bitvector_print(int flag, bitvector_t * vec)
    +{
    + unsigned int i;
    + int sz;
    + extern int rbcedebug;
    +
    + if ((rbcedebug & flag) == 0) {
    + return;
    + }
    + if (vec == NULL) {
    + printk("v<0>-NULL\n");
    + return;
    + }
    + printk("v<%d>-", sz = vec->size);
    + for (i = 0; i < sz; i++) {
    + printk("%c", test_bit(i, vec->bits) ? '1' : '0');
    + }
    + return;
    +}
    +#else
    +#define bitvector_print(x, y)
    +#endif
    +
    +#endif /* _RBCE_BITVECTOR_H */
    Index: linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_internal.h
    ===================================================================
    --- linux-2.6.12-rc3-ckrm5.orig/kernel/ckrm/rbce/rbce_internal.h 2005-05-05 09:38:03.000000000 -0700
    +++ linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_internal.h 2005-05-05 09:38:05.000000000 -0700
    @@ -51,6 +51,8 @@ struct named_obj_hdr {
    char *name;
    };

    +#include "rbce_bitvector.h"
    +
    #define GET_REF(x) ((x)->obj.referenced)
    #define INC_REF(x) (GET_REF(x)++)
    #define DEC_REF(x) (--GET_REF(x))
    @@ -185,14 +187,25 @@ enum op_token {
    TOKEN_OP_STATE = (__force op_token_t) (TOKEN_OP_GREATER_THAN+6),
    };

    -
    /*
    - * data structure rbce_private_data to hold the app_tag for a task.
    - * Expands later.
    + * data structure rbce_private_data holds the bit vector 'eval' which
    + * specifies if rules and terms of rules are evaluated against the task
    + * and if they were evaluated, bit vector 'true' holds the result of that
    + * evaluation.
    + *
    + * This data structure is maintained in a task, and the bitvectors are
    + * updated only when needed.
    + *
    + * Each rule and each term of a rule has a corresponding bit in the vector.
    *
    */
    struct rbce_private_data {
    + int evaluate; /* whether to evaluate rules or not ? */
    + int rules_version; /* rules_version at last evaluation */
    + bitvector_t *eval;
    + bitvector_t *true;
    char *app_tag;
    + char data[0]; /* bitvectors eval and true */
    };

    #define RBCE_DATA(tsk) ((struct rbce_private_data*)((tsk)->ce_data))
    Index: linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_main.c
    ===================================================================
    --- linux-2.6.12-rc3-ckrm5.orig/kernel/ckrm/rbce/rbce_main.c 2005-05-05 09:38:03.000000000 -0700
    +++ linux-2.6.12-rc3-ckrm5/kernel/ckrm/rbce/rbce_main.c 2005-05-05 09:38:05.000000000 -0700
    @@ -23,6 +23,7 @@
    */

    #include "rbce_internal.h"
    +#include "rbce_bitvector.h"

    MODULE_DESCRIPTION(RBCE_MOD_DESCR);
    MODULE_AUTHOR("Hubertus Franke, Chandra Seetharaman (IBM)");
    @@ -57,14 +58,17 @@ int termop_2_vecidx[RBCE_RULE_INVALID] =
    extern int errno;

    int rbce_enabled = 1;
    +const int use_persistent_state = 1;

    static LIST_HEAD(class_list);
    static struct list_head rules_list[CKRM_MAX_CLASSTYPES];
    static int gl_num_rules;
    static int gl_action, gl_num_terms;
    +static int gl_bitmap_version, gl_action, gl_num_terms;
    static int gl_allocated, gl_released;
    static struct rbce_rule_term *gl_terms;
    static int gl_rules_version;
    +static bitvector_t *gl_mask_vecs[NUM_TERM_MASK_VECTOR];
    static rwlock_t rbce_rwlock = RW_LOCK_UNLOCKED;
    /*
    * One lock to protect them all !!!
    @@ -78,6 +82,8 @@ static rwlock_t rbce_rwlock = RW_LOCK_UN

    /* ======================= Helper Functions ========================= */

    +static void optimize_policy(void);
    +
    static inline struct rbce_rule *find_rule_name(const char *name)
    {
    struct named_obj_hdr *pos;
    @@ -159,6 +165,8 @@ static int insert_rule(struct rbce_rule
    }
    gl_rules_version++;
    list_add_tail(&rule->obj.link, insert);
    + if (rbce_enabled)
    + optimize_policy();
    return 0;
    }

    @@ -337,9 +345,150 @@ static inline int __delete_rule(struct r
    module_put(THIS_MODULE);
    kfree(rule->obj.name);
    kfree(rule);
    + if (rbce_enabled && (gl_action & POLICY_ACTION_PACK_TERMS))
    + optimize_policy();
    return 0;
    }

    +/*
    + * Optimize the rule evaluation logic
    + *
    + * Caller must hold global_rwlock in write mode.
    + */
    +static void optimize_policy(void)
    +{
    + int i, ii;
    + struct rbce_rule *rule;
    + struct rbce_rule_term *terms;
    + int num_terms;
    + int bsize;
    + bitvector_t **mask_vecs;
    + int pack_terms = 0;
    + int redoall;
    +
    + /*
    + * Due to dynamic rule addition/deletion of rules the term
    + * vector can get sparse. As a result the bitvectors grow as we don't
    + * reuse returned indices. If it becomes sparse enough we pack them
    + * closer.
    + */
    +
    + pack_terms = (gl_action & POLICY_ACTION_PACK_TERMS);
    +
    + if (pack_terms) {
    + int nsz = ALIGN((gl_num_terms - gl_released),
    + POLICY_INC_NUMTERMS);
    + int newidx = 0;
    + struct rbce_rule_term *newterms;
    +
    + terms = gl_terms;
    + newterms =
    + kmalloc(nsz * sizeof(struct rbce_rule_term), GFP_ATOMIC);
    + if (newterms) {
    + for (ii = 0; ii < CKRM_MAX_CLASSTYPES; ii++) {
    + /* FIXME: check only for task class types */
    + list_for_each_entry_reverse(rule,
    + &rules_list[ii],
    + obj.link) {
    + rule->index = newidx++;
    + for (i = rule->num_terms; --i >= 0;) {
    + int idx = rule->terms[i];
    + newterms[newidx] = terms[idx];
    + rule->terms[i] = newidx++;
    + }
    + }
    + }
    + kfree(terms);
    + gl_allocated = nsz;
    + gl_released = 0;
    + gl_num_terms = newidx;
    + gl_terms = newterms;
    +
    + gl_action &= ~POLICY_ACTION_PACK_TERMS;
    + gl_action |= POLICY_ACTION_NEW_VERSION;
    + }
    + }
    +
    + num_terms = gl_num_terms;
    + bsize = gl_allocated / 8 + sizeof(bitvector_t);
    + mask_vecs = gl_mask_vecs;
    + terms = gl_terms;
    +
    + if (gl_action & POLICY_ACTION_NEW_VERSION) {
    + /* allocate new mask vectors */
    + char *temp = kmalloc(NUM_TERM_MASK_VECTOR * bsize, GFP_ATOMIC);
    +
    + if (!temp) {
    + return;
    + }
    + if (mask_vecs[0]) {/* index 0 has the alloc returned address */
    + kfree(mask_vecs[0]);
    + }
    + for (i = 0; i < NUM_TERM_MASK_VECTOR; i++) {
    + mask_vecs[i] = (bitvector_t *) (temp + i * bsize);
    + bitvector_init(mask_vecs[i], gl_allocated);
    + }
    + gl_action &= ~POLICY_ACTION_NEW_VERSION;
    + gl_action |= POLICY_ACTION_REDO_ALL;
    + gl_bitmap_version++;
    + }
    +
    + /* We do two things here at once
    + * 1) recompute the rulemask for each required rule
    + * we guarantee proper dependency order during creation time and
    + * by reversely running through this list.
    + * 2) recompute the mask for each term and rule, if required
    + */
    +
    + redoall = gl_action & POLICY_ACTION_REDO_ALL;
    + gl_action &= ~POLICY_ACTION_REDO_ALL;
    +
    + for (ii = 0; ii < CKRM_MAX_CLASSTYPES; ii++) {
    + /* FIXME: check only for task class types */
    + list_for_each_entry_reverse(rule, &rules_list[ii], obj.link) {
    + unsigned long termflag;
    +
    + if (!redoall && !rule->do_opt)
    + continue;
    + termflag = 0;
    + for (i = rule->num_terms; --i >= 0;) {
    + int j, idx = rule->terms[i];
    + struct rbce_rule_term *term = &terms[idx];
    + int vecidx = termop_2_vecidx[term->op];
    +
    + if (vecidx == -1) {
    + termflag |= term->u.deprule->termflag;
    + /* mark this term belonging to all
    + contexts of deprule */
    + for (j = 0; j < NUM_TERM_MASK_VECTOR;
    + j++) {
    + if (term->u.deprule->termflag
    + & (1 << j)) {
    + bitvector_set(idx,
    + mask_vecs
    + [j]);
    + }
    + }
    + } else {
    + termflag |= TERM_2_TERMFLAG(vecidx);
    + /* mark this term belonging to
    + a particular context */
    + bitvector_set(idx, mask_vecs[vecidx]);
    + }
    + }
    + for (i = 0; i < NUM_TERM_MASK_VECTOR; i++) {
    + if (termflag & (1 << i)) {
    + bitvector_set(rule->index,
    + mask_vecs[i]);
    + }
    + }
    + rule->termflag = termflag;
    + rule->do_opt = 0;
    + }
    + }
    + return;
    +}
    +
    /* ======================= Rule related Functions ========================= */

    /*
    @@ -984,6 +1133,25 @@ struct rbce_private_data *create_private
    return NULL;
    }

    +static inline
    +void reset_evaluation(struct rbce_private_data *pdata,int termflag)
    +{
    + /* reset TAG ruleterm evaluation results to pick up
    + * on next classification event
    + */
    + if (termflag >= NUM_TERM_MASK_VECTOR) {
    + printk(KERN_ERR "rbce:reset_evaluation: trying to access "
    + "past valid address\n");
    + return;
    + }
    + if (use_persistent_state && gl_mask_vecs[termflag]) {
    + bitvector_and_not( pdata->eval, pdata->eval,
    + gl_mask_vecs[termflag] );
    + bitvector_and_not( pdata->true, pdata->true,
    + gl_mask_vecs[termflag] );
    + }
    +}
    +
    int rbce_set_tasktag(int pid, char *tag)
    {
    char *tp;
    --

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-05-05 21:25    [W:0.046 / U:0.432 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site