Automatic Loop Unrolling not working with #pragma unroll #pragma


Mauricio Vasquez
 

Hello,

We are implementing a basic version of a router. In order to perform the routing process we implemented a bounded loop that iterates over all routing table entries looking for a match.

We also used the #pragma directives in order to let clang automatically unroll the loop, unfortunately when we try to inject the module (using hover) we get the "back-edge from insn 37 to 13" error, that according to my understanding means that there are loops in the code.

We have tried different versions of the pragma directives [1], but in all the cases we continue to get the same error.

The only workaround that we have found so far is to manually unroll the loop, but this is awful as it complicates the code readability and maintainability.

This is a portion of the code that gives the error:

#include <linux/ip.h>
#include <linux/bpf.h>
 
#define BPF_TRACE
#define ROUTING_TABLE_DIM 4
 
/*Routing Table Entry*/
struct rt_entry {
  u32 network;  //network: e.g. 192.168.1.0
  u32 netmask;  //netmask: e.g. 255.255.255.0
  u32 port;     //port of the router
};
 
BPF_TABLE("array", u32, struct rt_entry, routing_table, ROUTING_TABLE_DIM);
 
static int handle_rx(void *skb, struct metadata *md) {
  u8 *cursor = 0;
  struct ip_t *ip = cursor_advance(cursor, sizeof(*ip));
 
  int i = 0;
  struct rt_entry *rt_entry_p = 0;
  u32 ip_dst_masked = 0;
 
  //#pragma unroll
  #pragma clang loop unroll(full)
  for (i = 0; i < ROUTING_TABLE_DIM; i++) {
    rt_entry_p = routing_table.lookup(&i);
    if (rt_entry_p) {
      ip_dst_masked = ip->dst & rt_entry_p->netmask;
      if (ip_dst_masked == rt_entry_p->network) {
        goto FORWARD;
      }
    }
  }
 
DROP:
  return RX_DROP;
 
FORWARD:
  pkt_redirect(skb,md, rt_entry_p->port);
  return RX_REDIRECT;
}

Do you have any idea why clang is not unrolling that loop?

Thanks in advance,

Mauricio Vásquez B

[1] http://clang.llvm.org/docs/LanguageExtensions.html#loop-unrolling


Thomas Graf
 

On 7 December 2016 at 22:06, Mauricio Vasquez via iovisor-dev
<iovisor-dev@...> wrote:
BPF_TABLE("array", u32, struct rt_entry, routing_table, ROUTING_TABLE_DIM);

static int handle_rx(void *skb, struct metadata *md) {
u8 *cursor = 0;
struct ip_t *ip = cursor_advance(cursor, sizeof(*ip));

int i = 0;
struct rt_entry *rt_entry_p = 0;
u32 ip_dst_masked = 0;

//#pragma unroll
#pragma clang loop unroll(full)
for (i = 0; i < ROUTING_TABLE_DIM; i++) {
rt_entry_p = routing_table.lookup(&i);
Might be because you pass a pointer here?

if (rt_entry_p) {
ip_dst_masked = ip->dst & rt_entry_p->netmask;
if (ip_dst_masked == rt_entry_p->network) {
goto FORWARD;
}
}
}

DROP:
return RX_DROP;

FORWARD:
pkt_redirect(skb,md, rt_entry_p->port);
return RX_REDIRECT;
}

Do you have any idea why clang is not unrolling that loop?
It is working fine for us here and we're just using the standard unroll pragma:
https://github.com/cilium/cilium/blob/master/bpf/lib/l3.h#L131


Fulvio Risso
 

Dear Thomas,
definitely a good reason for not unrolling the loop.
Thanks,

fulvio

On 08/12/2016 15:12, Thomas Graf via iovisor-dev wrote:
On 7 December 2016 at 22:06, Mauricio Vasquez via iovisor-dev
<iovisor-dev@...> wrote:
BPF_TABLE("array", u32, struct rt_entry, routing_table, ROUTING_TABLE_DIM);

static int handle_rx(void *skb, struct metadata *md) {
u8 *cursor = 0;
struct ip_t *ip = cursor_advance(cursor, sizeof(*ip));

int i = 0;
struct rt_entry *rt_entry_p = 0;
u32 ip_dst_masked = 0;

//#pragma unroll
#pragma clang loop unroll(full)
for (i = 0; i < ROUTING_TABLE_DIM; i++) {
rt_entry_p = routing_table.lookup(&i);
Might be because you pass a pointer here?

if (rt_entry_p) {
ip_dst_masked = ip->dst & rt_entry_p->netmask;
if (ip_dst_masked == rt_entry_p->network) {
goto FORWARD;
}
}
}

DROP:
return RX_DROP;

FORWARD:
pkt_redirect(skb,md, rt_entry_p->port);
return RX_REDIRECT;
}

Do you have any idea why clang is not unrolling that loop?
It is working fine for us here and we're just using the standard unroll pragma:
https://github.com/cilium/cilium/blob/master/bpf/lib/l3.h#L131
_______________________________________________
iovisor-dev mailing list
iovisor-dev@...
https://lists.iovisor.org/mailman/listinfo/iovisor-dev


Mauricio Vasquez
 

Hello Thomas,

On 12/08/2016 09:12 AM, Thomas Graf wrote:
On 7 December 2016 at 22:06, Mauricio Vasquez via iovisor-dev
<iovisor-dev@...> wrote:
BPF_TABLE("array", u32, struct rt_entry, routing_table, ROUTING_TABLE_DIM);

static int handle_rx(void *skb, struct metadata *md) {
u8 *cursor = 0;
struct ip_t *ip = cursor_advance(cursor, sizeof(*ip));

int i = 0;
struct rt_entry *rt_entry_p = 0;
u32 ip_dst_masked = 0;

//#pragma unroll
#pragma clang loop unroll(full)
for (i = 0; i < ROUTING_TABLE_DIM; i++) {
rt_entry_p = routing_table.lookup(&i);
Might be because you pass a pointer here?
We have been analyzing it into more detail, effectively passing a pointer to that function prevents the loop unrolling. My guessing is that in some way the compiler thinks that the counter could be modify in that function then the unrolling is not possible.
We implemented the loop in the following way, it works. However we still consider that it is a workaround and that a solution without workarounds should exist.

#pragma unroll
for (int i = 0; i < ROUTING_TABLE_DIM; i++) {
int xxx = i;
rt_entry_p = routing_table.lookup(&xxx);
if (rt_entry_p) {
ip_dst_masked = ip->dst & rt_entry_p->netmask;
if (ip_dst_masked == rt_entry_p->network) {
goto FORWARD;
}
}
}

We think that this behavior is caused by the lack of the const qualifier for the key argument in the lookup function [1].

Thanks very much for your help.

Mauricio

[1] https://lists.iovisor.org/pipermail/iovisor-dev/2016-December/000559.html


if (rt_entry_p) {
ip_dst_masked = ip->dst & rt_entry_p->netmask;
if (ip_dst_masked == rt_entry_p->network) {
goto FORWARD;
}
}
}

DROP:
return RX_DROP;

FORWARD:
pkt_redirect(skb,md, rt_entry_p->port);
return RX_REDIRECT;
}

Do you have any idea why clang is not unrolling that loop?
It is working fine for us here and we're just using the standard unroll pragma:
https://github.com/cilium/cilium/blob/master/bpf/lib/l3.h#L131