Có thể lưu trữ con trỏ trong bộ nhớ dùng chung mà không sử dụng bù trừ không?

Question

Khi sử dụng bộ nhớ dùng chung, mỗi quá trình có thể chia vùng chia sẻ thành một vùng khác nhau trong không gian địa chỉ tương ứng. Điều này có nghĩa là khi lưu trữ con trỏ trong khu vực được chia sẻ, bạn cần phải store them as offsets khi bắt đầu khu vực được chia sẻ. Thật không may, điều này làm phức tạp việc sử dụng các hướng dẫn nguyên tử (ví dụ: nếu bạn đang cố viết một số lock free algorithm). Ví dụ: giả sử bạn có một loạt các nút được tính tham chiếu trong bộ nhớ dùng chung, được tạo bởi một người viết duy nhất. Các nhà văn định kỳ cập nhật một cách nguyên tử một con trỏ 'p' để trỏ đến một nút hợp lệ với số tham chiếu tích cực. Người đọc muốn viết nguyên tử thành 'p' bởi vì nó trỏ tới phần đầu của một nút (một cấu trúc) mà phần tử đầu tiên của nó là một số tham chiếu. Vì p luôn trỏ đến một nút hợp lệ, việc gia tăng số lượng ref là an toàn, và làm cho nó an toàn để dereference 'p' và truy cập các thành viên khác. Tuy nhiên, tất cả điều này chỉ hoạt động khi mọi thứ ở trong cùng một không gian địa chỉ. Nếu các nút và 'p' con trỏ được lưu trữ trong bộ nhớ chia sẻ, sau đó khách hàng phải chịu một điều kiện chủng tộc:

1. x = đọc p
2. y = x + bù đắp
3. Tăng refcount tại y

Trong bước 2, p có thể thay đổi và x không còn trỏ đến nút hợp lệ nữa. Cách giải quyết duy nhất tôi có thể nghĩ là bằng cách nào đó buộc tất cả các quy trình phải đồng ý về nơi để ánh xạ bộ nhớ dùng chung, do đó con trỏ thực thay vì dời gốc có thể được lưu trữ trong vùng mmap'd. Có cách nào để làm điều đó? Tôi thấy MAP_FIXED trong tài liệu mmap, nhưng tôi không biết làm cách nào tôi có thể chọn một địa chỉ an toàn.

Chỉnh sửa: Sử dụng lắp ráp nội tuyến và tiền tố 'khóa' trên x86 có thể có thể tạo "giá trị gia tăng ptr với bù đắp Y theo giá trị Z"? Tùy chọn tương đương trên các kiến ​​trúc khác? Đã không viết rất nhiều hội đồng, không biết nếu các hướng dẫn cần thiết tồn tại.

Answer 1

On mức thấp x86 inctruction nguyên tử có thể làm tất cả các bước cây này cùng một lúc:

1. x = đọc p
2. y = x + bù đắp Tăng
3. refcount tại y

// 
     mov edi, Destination 
     mov edx, DataOffset 
     mov ecx, NewData 
@Repeat: 
     mov eax, [edi + edx] //load OldData 
//Here you can also increment eax and save to [edi + edx]   
     lock cmpxchg dword ptr [edi + edx], ecx 
     jnz @Repeat 
// 

Answer 2

Chúng tôi có mã tương tự như mô tả sự cố của bạn. Chúng tôi sử dụng một tập tin ánh xạ bộ nhớ, bù đắp, và khóa tập tin. Chúng tôi đã không tìm thấy một thay thế.

Answer 3

Điều này không quan trọng trên Hệ thống UNIX; chỉ cần sử dụng các chức năng bộ nhớ chia sẻ:

shgmet, shmat, shmctl, shmdt

void * shmat (int shmid, const void * shmaddr, int shmflg);

shmat() gắn bộ nhớ chia sẻ phân khúc xác định bởi shmid vào không gian địa chỉ của quá trình gọi. Địa chỉ gắn được xác định bởi shmaddr với một trong những tiêu chí sau:

Nếu shmaddr là NULL, hệ thống chọn địa chỉ phù hợp (không sử dụng) mà tại đó để đính kèm phân khúc này.

Chỉ cần chỉ định địa chỉ của chính bạn tại đây; ví dụ. 0x20000000000

Nếu bạn shmget() sử dụng cùng khóa và kích thước trong mọi quá trình, bạn sẽ nhận được phân đoạn bộ nhớ chia sẻ cùng. Nếu bạn shmat() tại cùng địa chỉ, các địa chỉ ảo sẽ giống nhau trong tất cả các quy trình. Hạt nhân không quan tâm đến phạm vi địa chỉ mà bạn sử dụng, miễn là nó không xung đột với bất kỳ nơi nào nó gán cho mọi thứ. (Nếu bạn bỏ địa chỉ, bạn có thể thấy khu vực chung mà nó thích đặt mọi thứ; ngoài ra, hãy kiểm tra địa chỉ trên ngăn xếp và trả về từ malloc()/new [].)

Trên Linux, hãy đảm bảo root đặt SHMMAX trong/proc/sys/kernel/shmmax thành một số đủ lớn để chứa các phân đoạn bộ nhớ chia sẻ của bạn (mặc định là 32MB).

Đối với các hoạt động nguyên tử, bạn có thể lấy tất cả chúng từ nguồn hạt nhân Linux, ví dụ:

bao gồm/asm-x86/atomic_64.h

/* 
* Make sure gcc doesn't try to be clever and move things around 
* on us. We need to use _exactly_ the address the user gave us, 
* not some alias that contains the same information. 
*/ 
typedef struct { 
     int counter; 
} atomic_t; 

/** 
* atomic_read - read atomic variable 
* @v: pointer of type atomic_t 
* 
* Atomically reads the value of @v. 
*/ 
#define atomic_read(v)   ((v)->counter) 

/** 
* atomic_set - set atomic variable 
* @v: pointer of type atomic_t 
* @i: required value 
* 
* Atomically sets the value of @v to @i. 
*/ 
#define atomic_set(v, i)    (((v)->counter) = (i)) 


/** 
* atomic_add - add integer to atomic variable 
* @i: integer value to add 
* @v: pointer of type atomic_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic_add(int i, atomic_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addl %1,%0" 
        : "=m" (v->counter) 
        : "ir" (i), "m" (v->counter)); 
} 

64-bit:

typedef struct { 
     long counter; 
} atomic64_t; 

/** 
* atomic64_add - add integer to atomic64 variable 
* @i: integer value to add 
* @v: pointer to type atomic64_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic64_add(long i, atomic64_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addq %1,%0" 
        : "=m" (v->counter) 
        : "er" (i), "m" (v->counter)); 
} 

Answer 4

Bạn không nên sợ để tạo nên một địa chỉ một cách ngẫu nhiên, bởi vì hạt nhân sẽ chỉ từ chối các địa chỉ mà nó không thích (những cái xung đột). Xem shmat() câu trả lời của tôi ở trên, sử dụng 0x20000000000

Với mmap:

void * mmap (void * addr, chiều dài size_t, int prot, int cờ, int fd, off_t bù đắp);

Nếu addr không phải là NULL, thì hạt nhân coi đó là gợi ý về vị trí để đặt ánh xạ; trên Linux, ánh xạ sẽ được tạo ở ranh giới trang cao hơn tiếp theo. Địa chỉ của ánh xạ mới được trả lại là kết quả của cuộc gọi.

Đối số cờ sẽ xác định xem cập nhật các bản đồ có thể nhìn thấy quá trình khác lập bản đồ cùng khu vực, và liệu cập nhật được thực thông qua các nền tảng tập tin. Hành vi này được xác định bởi bao gồm chính xác một trong các giá trị sau đây trong cờ:

MAP_SHARED Chia sẻ bản đồ này. Bản cập nhật cho ánh xạ được hiển thị cho các quá trình khác ánh xạ tệp này và được chuyển đến tệp bên dưới.Tệp có thể không thực sự được cập nhật cho đến khi msync (2) hoặc munmap() được gọi.

LỖI

EINVAL Chúng tôi không thích addr, chiều dài, hoặc bù đắp (ví dụ, họ quá lớn, hoặc không phù hợp trên một ranh giới trang).

Answer 5

Thêm bù đắp cho con trỏ không tạo ra tiềm năng cho cuộc đua, nó đã tồn tại. Vì ít nhất không phải ARM và x86 có thể đọc một con trỏ một cách nguyên tử, sau đó truy cập vào bộ nhớ nó đề cập đến bạn cần bảo vệ truy cập con trỏ bằng khóa bất kể bạn có thêm bù hay không.