1# Copyright (c) Barefoot Networks, Inc. 2# Licensed under the Apache License, Version 2.0 (the "License") 3 4from p4_hlir.hlir import p4_header_instance, p4_table, \ 5 p4_conditional_node, p4_action, p4_parse_state 6from p4_hlir.main import HLIR 7import typeFactory 8import ebpfTable 9import ebpfParser 10import ebpfAction 11import ebpfInstance 12import ebpfConditional 13import ebpfCounter 14import ebpfDeparser 15import programSerializer 16import target 17from compilationException import * 18 19 20class EbpfProgram(object): 21 def __init__(self, name, hlir, isRouter, config): 22 """Representation of an EbpfProgram (in fact, 23 a C program that is converted to EBPF)""" 24 assert isinstance(hlir, HLIR) 25 assert isinstance(isRouter, bool) 26 assert isinstance(config, target.TargetConfig) 27 28 self.hlir = hlir 29 self.name = name 30 self.uniqueNameCounter = 0 31 self.config = config 32 self.isRouter = isRouter 33 self.reservedPrefix = "ebpf_" 34 35 assert isinstance(config, target.TargetConfig) 36 37 self.packetName = self.reservedPrefix + "packet" 38 self.dropBit = self.reservedPrefix + "drop" 39 self.license = "GPL" 40 self.offsetVariableName = self.reservedPrefix + "packetOffsetInBits" 41 self.zeroKeyName = self.reservedPrefix + "zero" 42 self.arrayIndexType = self.config.uprefix + "32" 43 # all array tables must be indexed with u32 values 44 45 self.errorName = self.reservedPrefix + "error" 46 self.functionName = self.reservedPrefix + "filter" 47 self.egressPortName = "egress_port" # Hardwired in P4 definition 48 49 self.typeFactory = typeFactory.EbpfTypeFactory(config) 50 self.errorCodes = [ 51 "p4_pe_no_error", 52 "p4_pe_index_out_of_bounds", 53 "p4_pe_out_of_packet", 54 "p4_pe_header_too_long", 55 "p4_pe_header_too_short", 56 "p4_pe_unhandled_select", 57 "p4_pe_checksum"] 58 59 self.actions = [] 60 self.conditionals = [] 61 self.tables = [] 62 self.headers = [] # header instances 63 self.metadata = [] # metadata instances 64 self.stacks = [] # header stack instances EbpfHeaderStack 65 self.parsers = [] # all parsers 66 self.deparser = None 67 self.entryPoints = [] # control-flow entry points from parser 68 self.counters = [] 69 self.entryPointLabels = {} # maps p4_node from entryPoints 70 # to labels in the C program 71 self.egressEntry = None 72 73 self.construct() 74 75 self.headersStructTypeName = self.reservedPrefix + "headers_t" 76 self.headerStructName = self.reservedPrefix + "headers" 77 self.metadataStructTypeName = self.reservedPrefix + "metadata_t" 78 self.metadataStructName = self.reservedPrefix + "metadata" 79 80 def construct(self): 81 if len(self.hlir.p4_field_list_calculations) > 0: 82 raise NotSupportedException( 83 "{0} calculated field", 84 self.hlir.p4_field_list_calculations.values()[0].name) 85 86 for h in self.hlir.p4_header_instances.values(): 87 if h.max_index is not None: 88 assert isinstance(h, p4_header_instance) 89 if h.index == 0: 90 # header stack; allocate only for zero-th index 91 indexVarName = self.generateNewName(h.base_name + "_index") 92 stack = ebpfInstance.EbpfHeaderStack( 93 h, indexVarName, self.typeFactory) 94 self.stacks.append(stack) 95 elif h.metadata: 96 metadata = ebpfInstance.EbpfMetadata(h, self.typeFactory) 97 self.metadata.append(metadata) 98 else: 99 header = ebpfInstance.EbpfHeader(h, self.typeFactory) 100 self.headers.append(header) 101 102 for p in self.hlir.p4_parse_states.values(): 103 parser = ebpfParser.EbpfParser(p) 104 self.parsers.append(parser) 105 106 for a in self.hlir.p4_actions.values(): 107 if self.isInternalAction(a): 108 continue 109 action = ebpfAction.EbpfAction(a, self) 110 self.actions.append(action) 111 112 for c in self.hlir.p4_counters.values(): 113 counter = ebpfCounter.EbpfCounter(c, self) 114 self.counters.append(counter) 115 116 for t in self.hlir.p4_tables.values(): 117 table = ebpfTable.EbpfTable(t, self, self.config) 118 self.tables.append(table) 119 120 for n in self.hlir.p4_ingress_ptr.keys(): 121 self.entryPoints.append(n) 122 123 for n in self.hlir.p4_conditional_nodes.values(): 124 conditional = ebpfConditional.EbpfConditional(n, self) 125 self.conditionals.append(conditional) 126 127 self.egressEntry = self.hlir.p4_egress_ptr 128 self.deparser = ebpfDeparser.EbpfDeparser(self.hlir) 129 130 def isInternalAction(self, action): 131 # This is a heuristic really to guess which actions are built-in 132 # Unfortunately there seems to be no other way to do this 133 return action.lineno < 0 134 135 @staticmethod 136 def isArrayElementInstance(headerInstance): 137 assert isinstance(headerInstance, p4_header_instance) 138 return headerInstance.max_index is not None 139 140 def emitWarning(self, formatString, *message): 141 assert isinstance(formatString, str) 142 print("WARNING: ", formatString.format(*message)) 143 144 def toC(self, serializer): 145 assert isinstance(serializer, programSerializer.ProgramSerializer) 146 147 self.generateIncludes(serializer) 148 self.generatePreamble(serializer) 149 self.generateTypes(serializer) 150 self.generateTables(serializer) 151 152 serializer.newline() 153 serializer.emitIndent() 154 self.config.serializeCodeSection(serializer) 155 serializer.newline() 156 serializer.emitIndent() 157 serializer.appendFormat("int {0}(struct __sk_buff* {1}) ", 158 self.functionName, self.packetName) 159 serializer.blockStart() 160 161 self.generateHeaderInstance(serializer) 162 serializer.append(" = ") 163 self.generateInitializeHeaders(serializer) 164 serializer.endOfStatement(True) 165 166 self.generateMetadataInstance(serializer) 167 serializer.append(" = ") 168 self.generateInitializeMetadata(serializer) 169 serializer.endOfStatement(True) 170 171 self.createLocalVariables(serializer) 172 serializer.newline() 173 174 serializer.emitIndent() 175 serializer.appendLine("goto start;") 176 177 self.generateParser(serializer) 178 self.generatePipeline(serializer) 179 180 self.generateDeparser(serializer) 181 182 serializer.emitIndent() 183 serializer.appendLine("end:") 184 serializer.emitIndent() 185 186 if isinstance(self.config, target.KernelSamplesConfig): 187 serializer.appendFormat("return {0};", self.dropBit) 188 serializer.newline() 189 elif isinstance(self.config, target.BccConfig): 190 if self.isRouter: 191 serializer.appendFormat("if (!{0})", self.dropBit) 192 serializer.newline() 193 serializer.increaseIndent() 194 serializer.emitIndent() 195 serializer.appendFormat( 196 "bpf_clone_redirect({0}, {1}.standard_metadata.{2}, 0);", 197 self.packetName, self.metadataStructName, 198 self.egressPortName) 199 serializer.newline() 200 serializer.decreaseIndent() 201 202 serializer.emitIndent() 203 serializer.appendLine( 204 "return TC_ACT_SHOT /* drop packet; clone is forwarded */;") 205 else: 206 serializer.appendFormat( 207 "return {1} ? TC_ACT_SHOT : TC_ACT_PIPE;", 208 self.dropBit) 209 serializer.newline() 210 else: 211 raise CompilationException( 212 True, "Unexpected target configuration {0}", 213 self.config.targetName) 214 serializer.blockEnd(True) 215 216 self.generateLicense(serializer) 217 218 serializer.append(self.config.postamble) 219 220 def generateLicense(self, serializer): 221 self.config.serializeLicense(serializer, self.license) 222 223 # noinspection PyMethodMayBeStatic 224 def generateIncludes(self, serializer): 225 assert isinstance(serializer, programSerializer.ProgramSerializer) 226 serializer.append(self.config.getIncludes()) 227 228 def getLabel(self, p4node): 229 # C label that corresponds to this point in the control-flow 230 if p4node is None: 231 return "end" 232 elif isinstance(p4node, p4_parse_state): 233 label = p4node.name 234 self.entryPointLabels[p4node.name] = label 235 if p4node.name not in self.entryPointLabels: 236 label = self.generateNewName(p4node.name) 237 self.entryPointLabels[p4node.name] = label 238 return self.entryPointLabels[p4node.name] 239 240 # noinspection PyMethodMayBeStatic 241 def generatePreamble(self, serializer): 242 assert isinstance(serializer, programSerializer.ProgramSerializer) 243 244 serializer.emitIndent() 245 serializer.append("enum ErrorCode ") 246 serializer.blockStart() 247 for error in self.errorCodes: 248 serializer.emitIndent() 249 serializer.appendFormat("{0},", error) 250 serializer.newline() 251 serializer.blockEnd(False) 252 serializer.endOfStatement(True) 253 serializer.newline() 254 255 serializer.appendLine( 256 "#define EBPF_MASK(t, w) ((((t)(1)) << (w)) - (t)1)") 257 serializer.appendLine("#define BYTES(w) ((w + 7) / 8)") 258 259 self.config.generateDword(serializer) 260 261 # noinspection PyMethodMayBeStatic 262 def generateNewName(self, base): # base is a string 263 """Generates a fresh name based on the specified base name""" 264 # TODO: this should be made "safer" 265 assert isinstance(base, str) 266 267 base += "_" + str(self.uniqueNameCounter) 268 self.uniqueNameCounter += 1 269 return base 270 271 def generateTypes(self, serializer): 272 assert isinstance(serializer, programSerializer.ProgramSerializer) 273 274 for t in self.typeFactory.type_map.values(): 275 t.serialize(serializer) 276 277 # generate a new struct type for the packet itself 278 serializer.appendFormat("struct {0} ", self.headersStructTypeName) 279 serializer.blockStart() 280 for h in self.headers: 281 serializer.emitIndent() 282 h.declare(serializer) 283 serializer.endOfStatement(True) 284 285 for h in self.stacks: 286 assert isinstance(h, ebpfInstance.EbpfHeaderStack) 287 288 serializer.emitIndent() 289 h.declare(serializer) 290 serializer.endOfStatement(True) 291 292 serializer.blockEnd(False) 293 serializer.endOfStatement(True) 294 295 # generate a new struct type for the metadata 296 serializer.appendFormat("struct {0} ", self.metadataStructTypeName) 297 serializer.blockStart() 298 for h in self.metadata: 299 assert isinstance(h, ebpfInstance.EbpfMetadata) 300 301 serializer.emitIndent() 302 h.declare(serializer) 303 serializer.endOfStatement(True) 304 serializer.blockEnd(False) 305 serializer.endOfStatement(True) 306 307 def generateTables(self, serializer): 308 assert isinstance(serializer, programSerializer.ProgramSerializer) 309 310 for t in self.tables: 311 t.serialize(serializer, self) 312 313 for c in self.counters: 314 c.serialize(serializer, self) 315 316 def generateHeaderInstance(self, serializer): 317 assert isinstance(serializer, programSerializer.ProgramSerializer) 318 319 serializer.emitIndent() 320 serializer.appendFormat( 321 "struct {0} {1}", self.headersStructTypeName, self.headerStructName) 322 323 def generateInitializeHeaders(self, serializer): 324 assert isinstance(serializer, programSerializer.ProgramSerializer) 325 326 serializer.blockStart() 327 for h in self.headers: 328 serializer.emitIndent() 329 serializer.appendFormat(".{0} = ", h.name) 330 h.type.emitInitializer(serializer) 331 serializer.appendLine(",") 332 serializer.blockEnd(False) 333 334 def generateMetadataInstance(self, serializer): 335 assert isinstance(serializer, programSerializer.ProgramSerializer) 336 337 serializer.emitIndent() 338 serializer.appendFormat( 339 "struct {0} {1}", 340 self.metadataStructTypeName, 341 self.metadataStructName) 342 343 def generateDeparser(self, serializer): 344 self.deparser.serialize(serializer, self) 345 346 def generateInitializeMetadata(self, serializer): 347 assert isinstance(serializer, programSerializer.ProgramSerializer) 348 349 serializer.blockStart() 350 for h in self.metadata: 351 serializer.emitIndent() 352 serializer.appendFormat(".{0} = ", h.name) 353 h.emitInitializer(serializer) 354 serializer.appendLine(",") 355 serializer.blockEnd(False) 356 357 def createLocalVariables(self, serializer): 358 assert isinstance(serializer, programSerializer.ProgramSerializer) 359 360 serializer.emitIndent() 361 serializer.appendFormat("unsigned {0} = 0;", self.offsetVariableName) 362 serializer.newline() 363 364 serializer.emitIndent() 365 serializer.appendFormat( 366 "enum ErrorCode {0} = p4_pe_no_error;", self.errorName) 367 serializer.newline() 368 369 serializer.emitIndent() 370 serializer.appendFormat( 371 "{0}8 {1} = 0;", self.config.uprefix, self.dropBit) 372 serializer.newline() 373 374 serializer.emitIndent() 375 serializer.appendFormat( 376 "{0} {1} = 0;", self.arrayIndexType, self.zeroKeyName) 377 serializer.newline() 378 379 for h in self.stacks: 380 serializer.emitIndent() 381 serializer.appendFormat( 382 "{0}8 {0} = 0;", self.config.uprefix, h.indexVar) 383 serializer.newline() 384 385 def getStackInstance(self, name): 386 assert isinstance(name, str) 387 388 for h in self.stacks: 389 if h.name == name: 390 assert isinstance(h, ebpfInstance.EbpfHeaderStack) 391 return h 392 raise CompilationException( 393 True, "Could not locate header stack named {0}", name) 394 395 def getHeaderInstance(self, name): 396 assert isinstance(name, str) 397 398 for h in self.headers: 399 if h.name == name: 400 assert isinstance(h, ebpfInstance.EbpfHeader) 401 return h 402 raise CompilationException( 403 True, "Could not locate header instance named {0}", name) 404 405 def getInstance(self, name): 406 assert isinstance(name, str) 407 408 for h in self.headers: 409 if h.name == name: 410 return h 411 for h in self.metadata: 412 if h.name == name: 413 return h 414 raise CompilationException( 415 True, "Could not locate instance named {0}", name) 416 417 def getAction(self, p4action): 418 assert isinstance(p4action, p4_action) 419 for a in self.actions: 420 if a.name == p4action.name: 421 return a 422 423 newAction = ebpfAction.BuiltinAction(p4action) 424 self.actions.append(newAction) 425 return newAction 426 427 def getTable(self, name): 428 assert isinstance(name, str) 429 for t in self.tables: 430 if t.name == name: 431 return t 432 raise CompilationException( 433 True, "Could not locate table named {0}", name) 434 435 def getCounter(self, name): 436 assert isinstance(name, str) 437 for t in self.counters: 438 if t.name == name: 439 return t 440 raise CompilationException( 441 True, "Could not locate counters named {0}", name) 442 443 def getConditional(self, name): 444 assert isinstance(name, str) 445 for c in self.conditionals: 446 if c.name == name: 447 return c 448 raise CompilationException( 449 True, "Could not locate conditional named {0}", name) 450 451 def generateParser(self, serializer): 452 assert isinstance(serializer, programSerializer.ProgramSerializer) 453 for p in self.parsers: 454 p.serialize(serializer, self) 455 456 def generateIngressPipeline(self, serializer): 457 assert isinstance(serializer, programSerializer.ProgramSerializer) 458 for t in self.tables: 459 assert isinstance(t, ebpfTable.EbpfTable) 460 serializer.emitIndent() 461 serializer.appendFormat("{0}:", t.name) 462 serializer.newline() 463 464 def generateControlFlowNode(self, serializer, node, nextEntryPoint): 465 # nextEntryPoint is used as a target whenever the target is None 466 # nextEntryPoint may also be None 467 if isinstance(node, p4_table): 468 table = self.getTable(node.name) 469 assert isinstance(table, ebpfTable.EbpfTable) 470 table.serializeCode(serializer, self, nextEntryPoint) 471 elif isinstance(node, p4_conditional_node): 472 conditional = self.getConditional(node.name) 473 assert isinstance(conditional, ebpfConditional.EbpfConditional) 474 conditional.generateCode(serializer, self, nextEntryPoint) 475 else: 476 raise CompilationException( 477 True, "{0} Unexpected control flow node ", node) 478 479 def generatePipelineInternal(self, serializer, nodestoadd, nextEntryPoint): 480 assert isinstance(serializer, programSerializer.ProgramSerializer) 481 assert isinstance(nodestoadd, set) 482 483 done = set() 484 while len(nodestoadd) > 0: 485 todo = nodestoadd.pop() 486 if todo in done: 487 continue 488 if todo is None: 489 continue 490 491 print("Generating ", todo.name) 492 493 done.add(todo) 494 self.generateControlFlowNode(serializer, todo, nextEntryPoint) 495 496 for n in todo.next_.values(): 497 nodestoadd.add(n) 498 499 def generatePipeline(self, serializer): 500 todo = set() 501 for e in self.entryPoints: 502 todo.add(e) 503 self.generatePipelineInternal(serializer, todo, self.egressEntry) 504 todo = set() 505 todo.add(self.egressEntry) 506 self.generatePipelineInternal(serializer, todo, None) 507