Increase MAX_TAIL_CALL_CNT from 32 to 33

[shpalani]

Describe the bug

Problem:

1. The current MAX_TAIL_CALL_CNT in ebpf-for-windows is 32.
2. The total number of tail calls supported is 31, excluding the top-level caller.

Proposal:

1. Increase MAX_TAIL_CALL_CNT to 33, to match Linux behavior.
2. Check the number of tail calls supported in Linux and match the behavior in ebpf-for-windows
   2.1 33 MAX_TAIL_CALL_CNT : 32 Tail Calls + 1 Top-level Caller
   Or,
   2.2 33 MAX_TAIL_CALL_CNT: 33 Tails Calls, excluding the Top-level Caller.
3. Fix the backend and test cases to match the increased MAX_TAIL_CALL_CNT

Please check #2496 where the problem was detected and reported.

OS information

Windows 10 and above

Steps taken to reproduce bug

Please check #2496 where the problem was detected and reported.
The test case to reproduce is in draft PR.

Expected behavior

MAX_TAIL_CALL_CNT should be 33.

Linux reference:
https://lore.kernel.org/stable/20220118021940.1942199-26-sashal@kernel.org/

Actual outcome

1. The current MAX_TAIL_CALL_CNT in ebpf-for-windows is 32.
2. The total number of tail calls supported is 31, excluding the top-level caller.

Additional details

No response

[shpalani]

Current status:

• Added max tail call test case and testing in
  https://github.com/Alan-Jowett/bpf_performance/pull/48

[shpalani]

Linux traces: (xdp_test_callee0 to xdp_test_callee32 is 33 Tail Calls)

        <...>-9564    [001] d...1 71617.292118: bpf_trace_printk: xdp_test_caller: Starting Tail callees with [MAX COUNT = 32]

       <...>-9564    [001] d...1 71617.292169: bpf_trace_printk: xdp_test_callee: Tail call index [**cur = 0**], [next = 1]

       <...>-9564    [001] d...1 71617.292171: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 1], [next = 2]

       <...>-9564    [001] d...1 71617.292172: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 2], [next = 3]

       <...>-9564    [001] d...1 71617.292179: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 3], [next = 4]

       <...>-9564    [001] d...1 71617.292180: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 4], [next = 5]

       <...>-9564    [001] d...1 71617.292182: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 5], [next = 6]

       <...>-9564    [001] d...1 71617.292183: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 6], [next = 7]

       <...>-9564    [001] d...1 71617.292184: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 7], [next = 8]

       <...>-9564    [001] d...1 71617.292186: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 8], [next = 9]

       <...>-9564    [001] d...1 71617.292187: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 9], [next = 10]

       <...>-9564    [001] d...1 71617.292189: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 10], [next = 11]

       <...>-9564    [001] d...1 71617.292190: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 11], [next = 12]

       <...>-9564    [001] d...1 71617.292192: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 12], [next = 13]

       <...>-9564    [001] d...1 71617.292193: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 13], [next = 14]

       <...>-9564    [001] d...1 71617.292195: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 14], [next = 15]

       <...>-9564    [001] d...1 71617.292197: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 15], [next = 16]

       <...>-9564    [001] d...1 71617.292198: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 16], [next = 17]

       <...>-9564    [001] d...1 71617.292200: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 17], [next = 18]

       <...>-9564    [001] d...1 71617.292277: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 18], [next = 19]

       <...>-9564    [001] d...1 71617.292280: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 19], [next = 20]

       <...>-9564    [001] d...1 71617.292282: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 20], [next = 21]

       <...>-9564    [001] d...1 71617.292283: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 21], [next = 22]

       <...>-9564    [001] d...1 71617.292285: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 22], [next = 23]

       <...>-9564    [001] d...1 71617.292287: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 23], [next = 24]

       <...>-9564    [001] d...1 71617.292289: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 24], [next = 25]

       <...>-9564    [001] d...1 71617.292290: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 25], [next = 26]

       <...>-9564    [001] d...1 71617.292292: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 26], [next = 27]

       <...>-9564    [001] d...1 71617.292293: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 27], [next = 28]

       <...>-9564    [001] d...1 71617.292295: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 28], [next = 29]

       <...>-9564    [001] d...1 71617.292297: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 29], [next = 30]

       <...>-9564    [001] d...1 71617.292298: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 30], [next = 31]

       <...>-9564    [001] d...1 71617.292301: bpf_trace_printk: xdp_test_callee: Tail call index [cur = 31], [next = 32]

       <...>-9564    [001] d...1 71617.292303: bpf_trace_printk: xdp_test_callee: Tail call index [**cur = 32**], [next = 33]

       <...>-9564    [001] d...1 71617.292304: bpf_trace_printk: Tail call failed at index 33

[shpalani]

Analysis/Conclusion:

<style> </style>

eBPF	Linux	Windows
MAX_TAIL_CALL_CNT	33	32
MAXIMUM NUMBER OF TAIL CALLEES	33	31
Top-Level Caller included	No	Current behavior of 32 =  31 (Callees) + 1 (Top-level included)
Performance 1 million iterations	bpf_tail_callee_max, -          287, 294	bpf_tail_callee_max,      120783, 120361

Next step to fix:

1. MAX_TAIL_CALL_CNT to 33
2. Fix the backend to process 33 tail callees.
3. Fix all the test cases which fail with new MAX_TAIL_CALL_CNT .