MAD MAD ACCESS PATTERN
MMAP USAGE
#include
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
return value: Pointer to the mapped area
addr: hint for kernel to choose the address to create mapping
0 let the kernel do the mapping itself length: ‘length’ bytes from start point (offset) fd: the file to be mapped
offset: the start point of mapping
• •
• •
•
• • •
MMAP
MEMORY-MAPPED FILE IO
Offset
addr length
HEAP
HEAP
STACK
Process Address Space (Virtual)
File Object fd
MAPPED PART
•
•
flag: Sharable
•
• MAP_SHARED
•
•
•
MMAP USAGE
prot: Protection
Like open files, you have to specify whether it can be read/write/exec
Share the mapping between different processes (by using fork/exec) MAP_PRIVATE
Update to a mapping (by one process) is not visible to other processes
•
•
Performance: Speed:
•
•
•
Data in memory, very fast Memory efficiency:
MMAP WHY
Multiple processes share only one segment of (physical)memory, not one for each(open file)
• Inter-Process Communication(IPC):
Can be shared between different processes
Fast to access, easy to use What is the disadvantage?
•
•
•
•
•
•
BINARY SEARCH TREE
typedef struct { uint32_t left_child;
uint32_t right_child; uint32_t count
float price
char word[0];
} BinaryTreeNode
• • • •
BINARY SEARCH TREE
left_child = offset I right_child = offset II
TEST
SAMPLE
offset II
LIST
offset I
BSRT TEST SAMPLE LIST
HOW TO TRAVERSE BINARY SEARCH TREE
Implementation with pointer is easy
How about the implementation with offset?
Think about how to advance to next one? You need a pointer to the start of the file
pointer + offset = next node
MMAP: You already have a pointer to start point
fget/fseek: SEEK_SET is the start of the file
• •
•
•
•
•
•
DIFFERENCE BETWEEN FSEEK & MMAP
Read Object
MMAP is already a pointer, you just need to cast it
(BinaryTreeNode*) ptr -> word
FSEEK/FGET: you have to read files and put data in an object
BinaryTreeNode* ptr = malloc( ??? ) fread( ptr, ???)
How many bytes to read? (HINT! You know everything but word[0])
•
•
•
•
•
• •
• •
•
•
Read the manage of mmap/fseek/fgetc/fread/offsetof How to time your program?
Go back to utilities_unleashed Understand how to traverse the tree first!
HINT