Link to home
Start Free TrialLog in
Avatar of FireBall
FireBall

asked on

Kernel module dynamic arrays

Hello ,

Normally we really love of using std::map on userspace but in kernel space i could not find a dynamic memory allocated map structure. Any body knows a good example how to do this job on kernel space ?

Thank you
Avatar of sarabande
sarabande
Flag of Luxembourg image

don't know what you mean by user space vs. kernel space.

if you can use c++ compiler you also should be able to use std::map. if you are forced to ansi c  or real time processing (or other which prevents from using STL) you should tell which kind of map you are looking for and which requirements you have.

Sara
Avatar of FireBall
FireBall

ASKER

i am sorry , i am using C
Kernel space does not support std libraries
and what are your requirements for key and value type? how many entries do you want to store in the map? does it grow dynamically or is it constant after initialization or load?

Sara
it will grow dynamically , and after 1 second i will delete entire array and recreate new one , so the number of the elements in the array is dynamic
note, in c you normally would use a sorted array and binary search as a substitute for a map.

Sara
how many entries? is there a reasonable maximum? what are the keys? and what the values?

Sara
There is no reasonable max. I am tracing the interface traffic if an huge ddos starts it goes on millions
if it is less than 100 entries you might use linear search which is as fast as binary search (and spares sorting).

Sara
it goes on millions

within 1 second? still don't know what you were needing for key and value. give a sample with at least 10 entries.

Sara
just in decimal format of ip addresses
did you use ip4 or ip6 as key and count the number of requests per ip?

Sara
ip4
you may use structures like

typedef struct IP4Count
{
     unsigned int ip4;
     unsigned int count;
} IP4Count;

typedef struct IP4Map
{
      IP4Count * a;
      size_t s;
      size_t n;
} IP4Map;

int compareIP4(unsigned int ip4_1, unsigned int ip4_2)
{
      return  (ip4_1 < ip4_2)? -1 : (ip4_1 > ip4_2)? 1 : 0;
}

Open in new window


Sara
ASKER CERTIFIED SOLUTION
Avatar of sarabande
sarabande
Flag of Luxembourg image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Thank you ,

I only do not understand this part , how it works

int compareIP4(unsigned int ip4_1, unsigned int ip4_2)
{
      return  (ip4_1 < ip4_2)? -1 : (ip4_1 > ip4_2)? 1 : 0;
}

Open in new window


and also please check my other question that you answered https://www.experts-exchange.com/questions/29053084/Simple-byte-to-uint-question.html?anchor=a42271144¬ificationFollowed=196621868&anchorAnswerId=42271144#a42271144
you would need a compare function if using a tool like quicksort (qsort) for sorting the array.

however, it should compare types IP4Count rather than ip4 numbers.

int compareIP4(IP4Count * ip4c1, IP4Count * ip4c2)
{
      return  (ip4c1->ip4 < ip4c2->ip4)? -1 : (ip4c1->ip4 > ip4c2->ip4)? 1 : 0;
}

Open in new window


but, if using the FindIp4InMap for inserting and incrementing you wouldn't need a sort function.

the find function would find the position in the array where the ip4 either already is or where it needs to be inserted. in the first case you simply would increment the counter of the IP4Count entry and in the second case you would move all entries right of the position by 1 and insert a new IP4Count entry with count 1. in both cases the array is still sorted and prepared to do a binary search.

Sara
Creating this functions will be so hard for me :)

typedef struct IP4Count
{
     unsigned int ip4;
     unsigned int count;
} IP4Count;

typedef struct IP4Map
{
      IP4Count * a;
      size_t s;
      size_t n;
} IP4Map;
int compareIP4(unsigned int ip4_1, unsigned int ip4_2)
{
      return  (ip4_1 < ip4_2)? -1 : (ip4_1 > ip4_2)? 1 : 0;
}
IP4Map * CreateMap(size_t initial);
int FindIP4InMap(IP4Map * ip4map, unsignd int ip4);
unsigned int AddIP4ToMap(IP4Map * ip4map, unsignd int ip4);
unsigned int GetCountFromMap(IP4Map * ip4map, unsignd int ip4);
void DeleteMap(IP4Map * ip4map);
IP4Count * GetNext(IP4Map * ip4map, IP4Count * ip4cPrev);

Open in new window

So should you help me for this :

IP4Map * CreateMap(size_t initial);


how should i make the size dynamic
static size_t blocksize = 1024;
IP4Map * CreateMap(size_t initial)
{
       IP4Map * pMap = (IP4Map *)malloc(sizeof(IP4Map));
       if (initial > 0 && blocksize != initial)
       {
            blocksize = initial;
       }
       pMap->a = (IP4Count *)malloc(sizeof(IP4Count)*blocksize);
       memset(pMap->a, 0, sizeof(IP4Count)*blocksize);
       pMap->s = blocksize;  // allocated size
       pMap->n = 0;    // number of elements  
       return pMap;   
}

Open in new window


Sara
I want to give your help's point if you answer this too : https://www.experts-exchange.com/questions/29053123/Strcut-Map-in-c.html
also please check your inbox

Thank you
implicit declaration of function ‘malloc’ [-Werror=implicit-function-declaration]

stdlib is not allowed in kernel space programming
how should i make the size dynamic


int FindIP4InMap(IP4Map * ip4map, unsigned int ip4)
{
      int beg = 0; 
      int end = ip4map->n;
      int mid = (beg + end)/2;
      while (end > begin)
      {
             if (ip4 < ip4map->a[mid].ip4)
             {
                    end = mid;
                    mid = (beg+end)/2;
             }
             else if (ip4 > ip4map->a[mid].ip4)
             {
                    beg = mid+1;                    
                    mid = (beg+end)/2;
             }
             else
             {
                   break;
             }
      }
      return mid;
};

unsigned int AddIP4ToMap(IP4Map * ip4map, unsignd int ip4)
{
       unsigned int pos =  0;
       // if the allocated array is full we grow the array by new blocksize elements
       if (ip4map->n >= ip4map->s)
       {
              ip4map->a = (IP4Count *)realloc( ip4map->a, ip4map->s+blocksize);
              memset(&ip4map->a[ip4map->s], 0, sizeof(IP4Count)*blocksize));
              ip4map->s += blocksize;
       }
       pos =   FindIP4InMap(ip4map, ip4);
       if (ip4map->n > pos)
       {
             // check if ip4 already exists at pos
             if (ip4map->a[pos].ip4 == ip4)
             {
                   return ++ip4map->a[pos].count;  // increment counter
             }
             else  // shift entries 1 to the right from pos 
             {
                    unsigned int shift = (ip4map->n - pos)-1;
                    if (shift > 0)
                    {
                          memmove(&ip4map->a[pos+1], &ip4map->a[pos], shift);
                    }
             }
        }
        ip4map->a[pos].ip4 = ip4;
        ip4map->a[pos].count = 1;
        ip4map->n++;
        return 1;
}

Open in new window


Sara
kmalloc solve the problem but final problem is where to call  Createmap , i have no main routine , how should i call create map in global process ?  I can not put it into init_module or into netfilter_ops because netfilter_ops is reworking in every packet and it will lost the collected data in my opinion


int init_module()
{	
        netfilter_ops.hook              =       main_hook;
        netfilter_ops.pf                =       PF_INET;        
        netfilter_ops.hooknum           =       NF_INET_PRE_ROUTING;
        netfilter_ops.priority          =       NF_IP_PRI_FIRST;
        nf_register_hook(&netfilter_ops);
		return 0; 
}

Open in new window


IP4Map * CreateMap(size_t initial){
       IP4Map * pMap = (IP4Map *)kmalloc(sizeof(IP4Map),GFP_NOWAIT);
       if (initial > 0 && blocksize != initial)
       {
            blocksize = initial;
       }
       pMap->a = (IP4Algo *)kmalloc(sizeof(IP4Algo)*blocksize,GFP_NOWAIT);
       memset(pMap->a, 0, sizeof(IP4Algo)*blocksize);
       pMap->s = blocksize;  
       pMap->n = 0;   
       return pMap;   
}

Open in new window

implicit declaration of function ‘malloc’    stdlib is not allowed in kernel space programming
ok. can you list the functions which are allowed. is there a substitute for malloc like printk is a substitute for printf?

Sara
kmalloc solve the problem

good. do you have a krealloc as well?

you would create the map in main function. or in a function called from main.

Sara
yes it is ok with kmalloc and returning no error when i called under the hook function , but final question where should i put the main map creator


IP4Map * Newmap = CreateMap(blocksize);
we would continue tomorrow. unfortunately i am on holidays in France and it is time to go to bed.

Sara
int main(int nargs, char * szargs[])
{
     // create an empty map with 1024 empty slots
     IP4Map * Newmap = CreateMap(1024); 
     

Open in new window


then pass NewMap to each subsequent map function.

Sara
typedef struct IP4Algo
{
     unsigned int ip4;
     unsigned int count;
} IP4Algo;


typedef struct IP4Map
{
      IP4Algo * a;
      size_t s;
      size_t n;
} IP4Map;
IP4Map * SYNMap;
int compareIP4(unsigned int ip4_1, unsigned int ip4_2)
{
      return  (ip4_1 < ip4_2)? -1 : (ip4_1 > ip4_2)? 1 : 0;
}
static size_t blocksize = 1024;
IP4Map * CreateMap(size_t initial);
IP4Map * CreateMap(size_t initial){
       IP4Map * pMap = (IP4Map *)kmalloc(sizeof(IP4Map),GFP_NOWAIT);
       if (initial > 0 && blocksize != initial)
       {
            blocksize = initial;
       }
       pMap->a = (IP4Algo *)kmalloc(sizeof(IP4Algo)*blocksize,GFP_NOWAIT);
       memset(pMap->a, 0, sizeof(IP4Algo)*blocksize);
       pMap->s = blocksize;  
       pMap->n = 0;   
       return pMap;   
}
int FindIP4InMap(IP4Map * ip4map, unsigned int ip4);
int FindIP4InMap(IP4Map * ip4map, unsigned int ip4)
{
      int beg = 0; 
      int end = ip4map->n;
      int mid = (beg + end)/2;
      while (end > begin)
      {
             if (ip4 < ip4map->a[mid].ip4)
             {
                    end = mid;
                    mid = (beg+end)/2;
             }
             else if (ip4 > ip4map->a[mid].ip4)
             {
                    beg = mid+1;                    
                    mid = (beg+end)/2;
             }
             else
             {
                   break;
             }
      }
      return mid;
};
unsigned int AddIP4ToMap(IP4Map * ip4map, unsigned int ip4);
unsigned int AddIP4ToMap(IP4Map * ip4map, unsigned int ip4)
{
       unsigned int pos =  0;
       // if the allocated array is full we grow the array by new blocksize elements
       if (ip4map->n >= ip4map->s)
       {
              ip4map->a = (IP4Algo *)realloc( ip4map->a, ip4map->s+blocksize);
              memset(&ip4map->a[ip4map->s], 0, sizeof(IP4Algo)*blocksize);
              ip4map->s += blocksize;
       }
       pos =   FindIP4InMap(ip4map, ip4);
       if (ip4map->n > pos)
       {
             // check if ip4 already exists at pos
             if (ip4map->a[pos].ip4 == ip4)
             {
                   return ++ip4map->a[pos].count;  // increment counter
             }
             else  // shift entries 1 to the right from pos 
             {
                    unsigned int shift = (ip4map->n - pos)-1;
                    if (shift > 0)
                    {
                          memmove(&ip4map->a[pos+1], &ip4map->a[pos], shift);
                    }
             }
        }
        ip4map->a[pos].ip4 = ip4;
        ip4map->a[pos].count = 1;
        ip4map->n++;
        return 1;
}

Open in new window


/home/Development/Kernel_Module/SPDGuard.c: In function ‘FindIP4InMap’:
/home/Development/Kernel_Module/SPDGuard.c:307:20: error: ‘begin’ undeclared (first use in this function)
       while (end > begin)
                    ^
/home/Development/Kernel_Module/SPDGuard.c:307:20: note: each undeclared identifier is reported only once for each function it appears in
/home/Development/Kernel_Module/SPDGuard.c: In function ‘AddIP4ToMap’:
/home/Development/Kernel_Module/SPDGuard.c:333:15: error: implicit declaration of function ‘realloc’ [-Werror=implicit-function-declaration]
               ip4map->a = (IP4Algo *)realloc( ip4map->a, ip4map->s+blocksize);

Open in new window

i have no main routine

then you have to make it a static pointer which is global. and call the create function in the init_module function.

Sara
I see it was beg and realloc is krealloc


please check your message box
typedef struct IP4Algo
{
     unsigned int ip4;
     unsigned int count;
} IP4Algo;

you would add a new unsigned int member for to save the TSVal.

Sara
Just rest :)

			AddIP4ToMap(SYNMap,ip_saddr);
			int cnt = FindIP4InMap(SYNMap,ip_saddr);
			printk(KERN_ERR "TEST|IP : %u , SYN : %d" ,ip_saddr,cnt);

Open in new window


result :

[10808.931189] TEST|IP : 634997477 , SYN : 0
[10808.931253] TEST|IP : 634997477 , SYN : 0
[10816.033749] TEST|IP : 634997477 , SYN : 0

Open in new window


I will check out why it does not counting
we have a long journey tomorrow. i will be back probably in 18 hours.

since i don't have an environment for kernel programming, i only can help with advice and c programming. but you probably will get the clue how to use the map as we will do it in a rather simple and straight-forward way.

Sara
ip_saddr

are you sure it is an unsigned int? if it is a string like "123.111.222.000" you would need to convert.

Sara
Thank you i have corrected it , one last question how should i delete and free the memory of an ip addr.
ok. i see it is an integer (you may use %u and not %d though).

the return of FindIP4InMap is not a counter but an index where the IP should be added to the array.

so the return of 0 is correct.

you may not call FindIP4InMap yourself but use the GetCountFromMap(IP4Map * ip4map, unsignd int ip4);

unsigned int GetCountFromMap(IP4Map * ip4map, unsignd int ip4)
{
       int pos = FindIP4InMap(ip4map, ip4);
       if (pos >= ip4map->n || ip4map->a[pos].ip4 != ip4)
       {
             return 0;  // not found in map
       }
       return ip4map->a[pos].count; 
}

Open in new window


Sara
how should i delete and free the memory of an ip addr.

void DeleteMap(IP4Map * ip4map)
{
      kfree(ip4map->a);
      kfree(ip4map);
}

Open in new window


you can't free a single ip beside you would add a function RemoveIp4FromMap, which would be similar to the add function but makes a left shift if the ip was found.

Sara
I will try thank you so much , you are a life saver