8
\$\begingroup\$

I am writing a java class file parsing & serialization library. As part of that i needed to implement a structure for the JVM bytecode instructions as well as come up with a way to parse & serialize these in an easy & generic way.

There are over 200+ instructions defined in the JVM bytecode spec and they have variable size due to operands. Due to my philosophy of how to write parsers (listed below as requirements for my solution) this turned out to be a bit of a challenge to deal with.

I looked up several open source implementations of JVM bytecode instructions and other types of instructions, but it seems basically everyone i could find solved it in a way I'd consider bad.

I had 3 key requirements for my solution.

  1. Avoid blatant memory waste: One of the most common ways i saw other projects implement their instruction structure was by either simply having a vector of U32s or a union. I do not want to just store every operand as the largest type however as I imagine it wastes quite a bit of memory even if it may technically be equally fast or faster, due to the way the CPU handles passing these values under the hood anyway.

  2. Fully parse the binary data into a real struct representation: The other most common way I saw instructions implemented was by simply not dealing with parsing operands into a ""real"" structure at all. Basically a lot of implementations would instead represent "instructions" as a single U32 offset into the classfile, which they'd keep loaded in memory. I do not want to keep the classfile or any part of it loaded after memory with structures that point back into it. I want everything to be parsed into real structures you'd interface with just like if it was an actual structure you had in your code.

  3. Avoid code repetition: The way a lot of the instructions dealt with the 200+ opcodes was by simply repeating the exact same line 200+ times. I definitely do not like this especially because you'd not only have to repeat those 200+ lines in one place, but in many places, such as the name function (GetOpcodeNames), enum, various constructors, serializer, parser, etc.

Anyway, here's my code which I think solves all these problems (but you may be able to find other problems with):

#include <vector>
#include <variant>
#include <cstdint>
#include <cassert>
#include <iostream>
#include <fstream>
#include <tuple>

using U8 = std::uint8_t;
using U16 = std::uint16_t;
using U32 = std::uint32_t;
using S8 = std::int8_t;
using S16 = std::int16_t;
using S32 = std::int32_t;

//macro that lets caller generate code for each JVM defined instruction, by passing their own macro (_OP). 
//For each instruction the instruction name, value, and thereafter operand types, are passed as arguments.  
//see example use in the OPCODE enum.
#define ITERATE_OPCODES( _OP )    \
  _OP(NOP,         0x00)          \
  _OP(RET,         0x01)          \
  _OP(BIPUSH,      0x03, U8)      \
  _OP(TABLESWITCH, 0x04, U16, U16) 
  //...repeat for all 200+ instructions

enum class OPCODE : U8
{
  #define _ENUM_ENTRY(OP, VAL, ...) OP = VAL,

  ITERATE_OPCODES( _ENUM_ENTRY )

  #undef _ENUM_ENTRY
};

//highlight why i like the macro use here. Notice what i can do in 11 lines which would otherwise be 200+
const char* GetOpcodeName(OPCODE op)
{
  switch(op)
  {
#define _CASE_ENTRY(OP, ...) case OPCODE::OP: return #OP;

    ITERATE_OPCODES( _CASE_ENTRY )

#undef _CASE_ENTRY
  };

  assert(false);
  return "";
}

struct Instruction
{
  OPCODE Opcode;

  using OperandT = std::variant<U8, U16, U32, S8, S16, S32>;
  std::vector<OperandT> Operands;


  template<typename... Args>
  Instruction(OPCODE opcode, Args&&... args): Opcode{opcode}
  {
    //TODO (looking for help on how to achieve this): validate operand types match corresponding operand type as defined in ITERATE_OPCODES, at compile time
    //e.g. for BIPUSH the variadic argument should have 1 argument in total and it should be of type U8
    (Operands.push_back(std::forward<Args>(args)), ...);
  }

  //stream parser for Instruction
  //TODO: theres some code duplication with the above constructor here
  //ideally i'd like to just read the opcode & operands then call the delegate constructor, to fix this.
  //However i cannot do this as the data is not constant.
  Instruction(std::istream& stream)
  {
    OPCODE opcode;
    stream.read(reinterpret_cast<char*>(&opcode), sizeof(opcode));

    switch(opcode)
    {
      #define _CASE_ENTRY(OP, VAL, ...) case OPCODE::OP:                           \
      {                                                                            \
        std::tuple<__VA_ARGS__> operands;                                          \
                                                                                   \
        std::apply([&](auto&&... args)                                             \
            {                                                                      \
               (stream.read(reinterpret_cast<char*>(&args), sizeof(args)), ...);   \
               (Operands.push_back( args ), ...);                                  \
            }, operands);                                                          \
                                                                                   \
      }break;

      ITERATE_OPCODES( _CASE_ENTRY )

      #undef _CASE_ENTRY

      default:  throw std::runtime_error{"unknown opcode encountered."};
    }

    Opcode = opcode;
  }
};

//helper template function for writing
template <typename T>
void Write(std::ostream& stream, const T& t)
{
  stream.write(reinterpret_cast<const char*>(&t), sizeof(T));
}

//stream serializer for Instruction 
std::ostream& operator<<(std::ostream& stream, const Instruction& instr)
{
  Write(stream, instr.Opcode);

  for(const Instruction::OperandT& operand : instr.Operands)
  {
    if(std::holds_alternative<U8>(operand))
      Write(stream, std::get<U8>(operand));

    else if(std::holds_alternative<U16>(operand))
      Write(stream, std::get<U16>(operand));

    else if(std::holds_alternative<U32>(operand))
      Write(stream, std::get<U32>(operand));

    else if(std::holds_alternative<S8>(operand))
      Write(stream, std::get<S8>(operand));

    else if(std::holds_alternative<S16>(operand))
      Write(stream, std::get<S16>(operand));

    else if(std::holds_alternative<S32>(operand))
      Write(stream, std::get<S32>(operand));

    else
      throw std::runtime_error{"serialize encountered unknown operand type."};
  }

  return stream;
}

In short: instructions use tagged unions (variants) for operands to avoid the memory waste problem, and I utilize macros to get around the code repetition problem. The parser constructor is a bit gnarly but basically manages to extract the operand type information into a tuple from __VA_ARGS__, read them using std::apply, and then pack them into the Operands vector with the correct type.

(If you know the JVM bytecode spec you'll notice there are some details that aren't handled, such as wide instructions or the more complex operands; I removed the code that handles that to keep it simple for reviewers to just review the base structure).

Quick rebuttal about the macros: I can already tell this is the thing people are going to scream at me. "UGLY MACROS UGLY MACROS!!!". Yes I understand macros are ugly but it seems to be my only solution here due to C++17's lack of reflection. If the choice is between repeating the same statement 200+ x 5 times or use a macro to just generate this thing, then isn't this the ONE place where using macros are acceptable? If at all macros are acceptable in any scenario wouldn't it be here?

\$\endgroup\$
2
  • 5
    \$\begingroup\$ You may find that using a 32-bit word per instruction is best on architectures that implement byte-addressing using a read-modify-write cycle. As to the macro, I think that it's eminently suited to this kind of thing - but would appreciate #undef ITERATE_OPCODES once we're done with it! \$\endgroup\$ Commented Jul 5, 2023 at 12:54
  • \$\begingroup\$ @p0sa Can you take a look at this? I made my own implementation based on your idea but I must confess I am strongly against MACRO abuse. So, i tried implementing your requirements without it. codereview.stackexchange.com/questions/285975/… \$\endgroup\$ Commented Jul 8, 2023 at 14:40

2 Answers 2

8
\$\begingroup\$

std::variant vs union

  1. Avoid blatant memory waste: One of the most common ways i saw other projects implement their instruction structure was by either simply having a vector of U32s or a union. I do not want to just store every operand as the largest type however as I imagine it wastes quite a bit of memory [...]

But std::variant is not better than union when it comes to memory usage; in fact std::variant is exactly a union of its types plus another member that tracks which of the types is active.

sizeof(OperandT) will be 8 bytes, since the largest type it can store is 4 bytes, but because of the tag field and alignment restrictions, it will now be 8 bytes.

Suppose you have an instruction though with two operands, then the Instruction object itself will use 32 bytes on 64-bit machines: 24 for the std::vector, and one byte for Opcode, but due to alignment the whole Instruction will be padded to 32 bytes. However, the std::vector will do a heap memory allocation to hold the two operands, so it will use another 16 bytes, plus whatever bookkeeping is needed behind the scenes to keep track of heap allocations. So in total I think it will use about 64 bytes.

I'm not sure what the maximum number of operands is, but if it's 3, then consider writing:

struct Instruction {
    OPCODE Opcode,
    union { U8, …, S32 } Operands[3];
    …
};

This will use only 16 bytes and does not do any heap allocations. It doesn't store the type of each individual operand, but in principle you know from the Opcode what the type of each operand is.

Use a visitor in operator<<()

You used the macros to avoid code duplication, but in operator<<() you have some code duplication as well that you did not address. You can avoid that by using a visitor:

for (auto& operand: instr.Operands)
{
    std::visit([](auto& value){ Write(stream, value); }, operand);
}
\$\endgroup\$
6
\$\begingroup\$

Some style critique from me (the principles seem sound).

Since the standard headers are independent of each other, we can include them in a consistent order. I prefer alphabetical, but you could choose Christmas-tree order or anything else predictable, so that it's easy to quickly confirm what's already included.

Those usings for the fixed-width types aren't going to end up in a header file, I hope? I'm not a fan of all-caps names for things that are not macros - the valuable shoutiness is diluted when we do that.

Definitely don't name OPCODE in all-caps.


In the stream constructor of Instruction, I would prefer not to have a default case, as this inhibits compiler checking that it's complete (very minor consideration, given we're using ITERATE_OPCODES). We can do that by assigning to the member Opcode early on (we don't need local opcode at all):

struct Instruction
{
  OPCODE Opcode = Opcode::NOP;
  ⋮
  
  Instruction(std::istream& stream)
  {
    stream.read(reinterpret_cast<char*>(&Opcode), sizeof Opcode);

    auto read_instruction = [&stream, this](auto&&... args) {
        (stream.read(reinterpret_cast<char*>(&args), sizeof args),...);
        (Operands.push_back(args),...);};

    switch(Opcode)
    {
#define _CASE_ENTRY(OP, VAL, ...)               \
        case OPCODE::OP:                        \
      {                                         \
        std::tuple<__VA_ARGS__> operands;       \
        std::apply(read_instruction, operands); \
        return;                                 \
      }

      ITERATE_OPCODES( _CASE_ENTRY )

#undef _CASE_ENTRY
    }

    throw std::runtime_error{"unknown opcode encountered."};
  }
};

If the throw is reached, the Instruction will be destructed anyway.

We might consider setting the stream to throw exceptions, rather than having to examine the stream after each read - but that's a concern for the next level up, I think.

For the other constructor, we certainly want to validate the number of arguments. We should be able to do that using ITERATE_OPCODES() with perhaps std::tuple_size<std::tuple<__VA_ARGS__>> or your own argument-counting template value.

\$\endgroup\$
2
  • \$\begingroup\$ What is a chirstmas tree order? I am super curious \$\endgroup\$ Commented Jul 7, 2023 at 17:46
  • \$\begingroup\$ That's in order of length - I don't find it particularly useful, and I'm not convinced its advocates are entirely serious. \$\endgroup\$ Commented Jul 7, 2023 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.