-1

I'm having trouble splitting a stored address into its components (namely into the tag bits, set index bits, and block offset bits). I'm trying to implement the function...

unsigned char check_cache(line cache[4], unsigned char addr);

This function will check whether the given cache stores the data at the given memory address. If the cache stores the data at the given memory address (i.e., cache hit), this function will return the stored data. Otherwise (i.e., cache miss), this function will return 0xFF. Here's some of the C code...

typedef struct {
        char valid;
        char tag;
        char block[4];
} line;

unsigned char check_cache(line cache[4], unsigned char addr);
  • The cache is directed-mapped (E=1), with a 4-byte block size (B=4) and four sets (S=4).

I need to store the given memory address in a byte-sized register and then split the address into three components (tag bits, set index bits, and block offset bits). Also, "You may want to use bit-level operations such as andb and shrb and 1-byte move instruction movb to split the address."

Here is my IA32 assembly code thus far

.global check_cache

check_cache:
   pushl   %ebp
   movl    %esp, %ebp

   movl    12(%ebp), %eax
   movl    $0x3, %ebx
   andl    %eax, %ebx
   shrl    $0x2, %eax
   movl    $0x3, %ecx
   andl    %eax, %ecx
   shrl    $0x2, %eax
   movl    $0xF, %edx
   andl    %eax, %edx

   popl    %ebp
   ret

I'm not sure where I'm going wrong here, but I'm getting a segmentation fault. %eax is meant to store the whole address, %ebx is meant to store the tag bits, %ecx is meant to store the index bits, and %edx is meant to store the block offset bits.

It's suggested to use the aforementioned bit-level operations, but can't I do this without using those?

Any help would be amazing. Thanks

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Bradley
  • 1
  • 1
    segfault on which instruction? Unless you used `.code32` to assemble 32-bit machine code into an executable that will run in 64-bit mode, there's no way the code you've shown can fault (except if it's jumped to with an invalid ESP, or stack overflow or underflow). (And `push %ebp` wouldn't assemble in 64-bit code). So this doesn't look like a [mcve], and you haven't provided any debug details from GDB or whatever. Simple ALU Instructions with just registers and immediate constants can't segfault. – Peter Cordes Nov 23 '21 at 12:48

1 Answers1

0

Perhaps you have a problem with function signature.

unsigned char check_cache(line cache[4], unsigned char addr);

You take a single byte instead of address by taking unsigned char addr.

The segmentation fault is likely to be caused by this instruction, as no other instructions perform indirection

   movl    12(%ebp), %eax

(well pushl/popl also do, they may fault if the stack is corrupted)

The instruction looks right (modulo passing only char instead of 32-bit address), but apparently the caller didn't fill a pointer there. So, check your caller:

  • Do you use 32-bit compilation?
  • Do you use the usual cdecl calling convention?
Alex Guteniev
  • 12,039
  • 2
  • 34
  • 79
  • This code is simulating a tiny cache that uses 8-bit addresses. *The cache is directed-mapped (E=1), with a 4-byte block size (B=4) and four sets (S=4).* I think `uint8_t` aka `unsigned char` is actually appropriate for it. Notice the struct uses (signed) `char tag`, so this isn't a tiny cache for a 32-bit address-space. – Peter Cordes Nov 23 '21 at 12:45
  • IDK how this could be segfaulting either. `push %ebp` wouldn't assemble in 64-bit mode, so that rules out that idea unless this isn't a [mcve] and there's actually a `.code32` somewhere to let it assemble 32-bit machine code into a 64-bit object file / executable. Either that or the segfault is actually somewhere else. – Peter Cordes Nov 23 '21 at 12:47
  • @PeterCordes, then should it be `movzbl`/`movsbl` to get a byte into `eax` with clearing high bits? – Alex Guteniev Nov 23 '21 at 12:53
  • 2
    If called by code generated by GCC or clang, it doesn't *need* to, because they [implement an undocumented extension to the calling convention](https://stackoverflow.com/questions/36706721/is-a-sign-or-zero-extension-required-when-adding-a-32bit-offset-to-a-pointer-for/36760539#36760539) where narrow args are sign- or zero-extended to 32-bit. clang even makes asm that depends on that, so fun fact, it's not ABI compatible with ICC. – Peter Cordes Nov 23 '21 at 12:58
  • 1
    But anyway, yeah I assume that's why the assignment the querent is attempting suggested using byte operations like `movb` and `shrb`. (`movzbl 12(%ebp), %eax` would be better than `movb` for performance though, avoiding a false dependency on modern CPUs, even if you still use byte operand-size for register RMWs like `and $3, %al`) – Peter Cordes Nov 23 '21 at 12:59
  • @AlexGuteniev Here is how I'm compiling... `gcc -Wall -g -m32 -c cache.c` `gcc -Wall -g -m32 -c prog3.s` `gcc -Wall -g -m32 -o xtest cache.o prog3.o` After going through the code, the first line moving 12(%ebp) into eax doesn't cause a segfault, but the second line seems to be the issue. I imagine the rest of the similar lines have the same problem. – Bradley Nov 23 '21 at 13:31
  • @PeterCordes I was trying to avoid using bit-level operations like movb and shrb because I've simply never used them before; is there any chance you know of a good resource for understanding these operations? I'm having trouble finding a good resource. – Bradley Nov 23 '21 at 13:35
  • @Bradley: You're already using `shrl $0x2, %eax` which is the same bit-shift operation as `shrb $0x2, %al`, except on a full 32-bit register instead of 8-bit. If you're value is already *zero*-extended into EAX, you'll be shifting zeros into the low 8 bits with `shr` so you can cmpb against the tag. As far as resources, the manual (https://www.felixcloutier.com/x86/sal:sar:shl:shr) shows you the forms of shift instructions available on x86. (But uses Intel-syntax). Of course for register operands, the operand-size suffix is redundant, most people would just write `shr $2, %al` or `%eax`. – Peter Cordes Nov 23 '21 at 13:44
  • @Bradley, are you saying `movl $0x3, %ebx` causes segmentation fault? I don't think this is possible. source `$0x3` is an immediate, dest `%ebx` is a register, there are no memory operand at all. – Alex Guteniev Nov 23 '21 at 13:47
  • @AlexGuteniev Figured out my issue with that line was that I didn't write `pushl %ebx` after initializing the stack (not exactly understanding why that is necessary, but it seemed to fix my issue) – Bradley Nov 23 '21 at 14:09
  • @Bradley, saving previous `%ebp` on stack is needed to create a stack frame, that you can push the stuff on stack and address parameters and local variables relative to %ebp`. The very `push %ebp` instruction is there so that you can overwrite `%ebp` with a new value, and then restore it. Stack frame is not strictly necessary here, but by omitting only this push operation you break the stack balance. – Alex Guteniev Nov 23 '21 at 14:21
  • Voting to close as not reproducible – Alex Guteniev Nov 23 '21 at 14:22