Kaip priskirti suderintą atmintį tik naudojant standartinę biblioteką?

Bandymą baigiau kaip interviu dalį, o vienas klausimas mane supainiojo - netgi su „Google“. Norėčiau pamatyti, ką gali atlikti stackoverflow:

„Memset_16aligned“ funkcijai reikalingas 16 baitų nukreiptas žymeklis, kuris jam perduotas, arba jis veiks.

a) Kaip paskirstytumėte 1024 baitų atminties ir suderintumėte ją su 16 baitų riba?
b) atlaisvindami atmintį, atlikę funkciją „memset_16“.

 { void *mem; void *ptr; // answer a) here memset_16aligned(ptr, 0, 1024); // answer b) here } 
358
23 окт. JimDaniel nustatė spalio 23 d 2008-10-23 02:23 '08, 02:23, 2008-10-23 02:23
@ 17 atsakymų

Originalus atsakymas

 { void *mem = malloc(1024+16); void *ptr = ((char *)mem+16)  ~ 0x0F; memset_16aligned(ptr, 0, 1024); free(mem); } 

Fiksuotas atsakymas

 { void *mem = malloc(1024+15); void *ptr = ((uintptr_t)mem+15)  ~ (uintptr_t)0x0F; memset_16aligned(ptr, 0, 1024); free(mem); } 

Paaiškinimas paprašius

Pirmas žingsnis yra skirti pakankamai laisvos vietos tik tuo atveju. Kadangi atmintis turi būti suderinta su 16 baitų (tai reiškia, kad aukšto baito adresas turi būti 16 kartų daugesnis), pridėjus 16 papildomų baitų, mes turime pakankamai vietos. Kažkur per pirmuosius 16 baitų yra 16 baitų nukreiptas žymeklis. (Atkreipkite dėmesį, kad malloc() turi grąžinti rodiklį, kuris yra pakankamai suderintas bet kokiam tikslui, tačiau „bet kokia“ reikšmė iš esmės reiškia pagrindinio tipo dalykus - long , double , long double , long long ir nuorodas į objektus ir nuorodas į Kai atliekate daugiau specializuotų dalykų, pavyzdžiui, žaidžiate su grafikos sistemomis, gali prireikti tiksliau suderinti juos su likusia sistema, taigi, tokie klausimai ir atsakymai.)

Kitas žingsnis yra konvertuoti tuščią rodyklę į char rodyklę; Persijos įlankos bendradarbiavimo taryba, tačiau neturėtumėte daryti aritmetinių nuorodų į negaliojančius rodiklius (ir Persijos įlankos bendradarbiavimo taryba turi įspėjimų, kad praneštumėte, kai piktnaudžiaujate). Tada pridėkite 16 į pradžios indeksą. Tarkime, kad malloc() grąžina neįtikėtinai prastą rodyklę: 0x800001. Įrašyta 16 suteikia 0x800011. Dabar noriu pereiti prie 16 baitų ribos - todėl noriu atstatyti paskutinius 4 bitus į 0. 0x0F turi paskutinius 4 bitus, nustatytus vienai; todėl ~0x0F turi visus bitus, išskyrus paskutinius keturis. Anding, kad su 0x800011 suteikia 0x800010. Galite kartoti per kitas kompensacijas ir matyti, kad tie patys aritmetiniai darbai.

Paskutinis žingsnis, free() , yra paprastas: jūs visada grįšite į free() vertę, kurią jums grąžins vienas iš malloc() , calloc() arba realloc() - visa kita yra katastrofa, teisingai realloc() mem įrašyti šią vertę - ačiū. Tai išlaisvina jį.

Galiausiai, jei žinote apie savo „ malloc sistemos paketo vidinius komponentus, galite daryti prielaidą, kad jis gali grąžinti 16 baitų suderintus duomenis (arba jis gali būti suderintas su 8 baitais). Jei jis buvo suderintas su 16 baitų, jums nereikės rašyti vertybių. Tačiau tai yra keistai, o ne nešiojamai - kitiems „ malloc paketams yra skirtingi minimalūs lygmenys, todėl vienas dalykas priimamas, kai dar kažkas darys pagrindinius sąvartynus. Per plačius apribojimus šis sprendimas yra nešiojamas.

Kažkas paminėjo posix_memalign() kaip kitą būdą gauti suderintą atmintį; kurios nėra prieinamos visur, bet dažnai gali būti įgyvendinamos naudojant tai kaip pagrindą. Atkreipkite dėmesį, kad derinimas buvo patogus 2; kiti derinimai yra nepatogesni.

Kitas komentaras - šis kodas nepatvirtina, kad atranka buvo sėkminga.

Keisti

„Windows“ programuotojas nurodė, kad negalite atlikti bitmap masės ant rodyklių, ir, iš tiesų, GCC (3.4.6 ir 4.3.1 testai) skundžiasi taip. Taigi, turėtumėte pakeisti pakeistą pagrindinio kodo versiją, konvertuotą į pagrindinę programą. Aš taip pat turėjau laisvę pridėti tik 15, o ne 16, kaip nurodyta. Aš naudoju uintptr_t nes C99 yra pakankamai ilgas, kad jis būtų prieinamas daugelyje platformų. Jei printf() pareiškimuose nebuvo PRIXPTR , #include <stdint.h> užtenka #include <stdint.h> vietoj #include <inttypes.h> . [Į šį kodą įeina korekcija, kurią nurodė , kuri pakartojo tašką, kurį anksčiau padarė Bill K prieš keletą metų.

 #include <assert.h> #include <inttypes.h> #include <stdio.h> #include <stdlib.h> #include <string.h> static void memset_16aligned(void *space, char byte, size_t nbytes) { assert((nbytes  0x0F) == 0); assert(((uintptr_t)space  0x0F) == 0); memset(space, byte, nbytes); // Not a custom implementation of memset() } int main(void) { void *mem = malloc(1024+15); void *ptr = (void *)(((uintptr_t)mem+15)  ~ (uintptr_t)0x0F); printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr); memset_16aligned(ptr, 0, 1024); free(mem); return(0); } 

Ir čia yra šiek tiek labiau apibendrinta versija, kuri bus taikoma dydžiams, kurių talpa yra 2:

 #include <assert.h> #include <inttypes.h> #include <stdio.h> #include <stdlib.h> #include <string.h> static void memset_16aligned(void *space, char byte, size_t nbytes) { assert((nbytes  0x0F) == 0); assert(((uintptr_t)space  0x0F) == 0); memset(space, byte, nbytes); // Not a custom implementation of memset() } static void test_mask(size_t align) { uintptr_t mask = ~(uintptr_t)(align - 1); void *mem = malloc(1024+align-1); void *ptr = (void *)(((uintptr_t)mem+align-1)  mask); assert((align  (align - 1)) == 0); printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr); memset_16aligned(ptr, 0, 1024); free(mem); } int main(void) { test_mask(16); test_mask(32); test_mask(64); test_mask(128); return(0); } 

Norint konvertuoti test_mask() į bendrosios paskirties paskirstymo funkciją, vienintelė grąžinimo vertė iš skirstytuvo turėtų koduoti išleidimo adresą, kaip nurodė keli žmonės jų atsakymuose.

Problemos su interviu dalyviais

Uri pakomentavo: Galbūt šį rytą turiu problemų su skaitymu, tačiau jei interviu klausimas konkrečiai nurodo: „Kaip priskirtumėte 1024 baitų atminties“, ir jūs aiškiai skiriate daugiau nei tai. Ar tai yra automatinis apklausos dalyvio gedimas?

Mano atsakymas netinka 300 simbolių komentarui ...

Tai priklauso nuo manau. Manau, kad dauguma žmonių (įskaitant mane) uždavė klausimą: "Kaip paskirstytumėte erdvę, kurioje galite saugoti 1024 baitų duomenų, o bazinis adresas yra 16 baitų kartotinis." Jei interviu davėjas iš tikrųjų reiškė, kaip galite skirti 1024 baitus (tik) ir suderinti su 16 baitų, tuomet galimybės yra ribotos.

  • Akivaizdu, kad viena galimybė yra paskirti 1024 baitus, o po to suteikti šį adresą „derinimas“; Šio požiūrio problema yra ta, kad faktinė turima erdvė nėra tinkamai apibrėžta (naudinga erdvė yra tarp 1008 ir 1024 baitų, tačiau nebuvo mechanizmo, pagal kurį būtų galima nustatyti, kokio dydžio), todėl jis mažiau naudingas.
  • Kita galimybė - rašyti visą atminties paskirstytuvą ir įsitikinti, kad 1024 baitų blokas, kurį grįžtate, yra tinkamai suderintas. Jei taip, jūs tikriausiai baigsite kažką panašaus į tai, kas buvo pasiūlyta, bet paslėpsite ją platintojo viduje.

Tačiau, jei apklausėjas tikisi bet kurio iš šių atsakymų, tikiuosi, kad jie supras, jog šis sprendimas atsako į glaudų klausimą, o tada peržiūri mano klausimą, kad pokalbis būtų nukreiptas teisinga kryptimi. (Be to, jei apklausėjas iš tikrųjų manė, kad nenoriu dirbti, jei atsakymas į nepakankamai tikslų reikalavimą būtų sumažintas ugnimi be pataisos, tuomet apklausėjas nėra tas, kuriam saugu dirbti.)

Pasaulis juda

Klausimo pavadinimas neseniai pasikeitė. Tai išsprendė atminties sutapimą C klausime, kuris mane pykdė. Pataisyta antraštė (Kaip priskirti suderintą atmintį tik naudojant standartinę biblioteką?) Reikia šiek tiek pataisyto atsakymo - šis papildymas suteikia jį.

C11 (ISO / IEC 9899: 2011) pridėta aligned_alloc() funkcija:

7.22.3.1

Santrauka

 #include <stdlib.h> void *aligned_alloc(size_t alignment, size_t size); 

Aprašymas
aligned_alloc funkcija skiria erdvę objektui, kurio išlygiavimas yra nurodytas aligned_alloc , kurio dydis nurodomas pagal size ir kurio vertė yra neapibrėžta. alignment reikšmė turi būti tinkama derinimas, kurį palaiko įgyvendinimas, o size vertė turi būti lygiavertis skaičiaus kelis kartus.

Grąžina
aligned_alloc funkcija grąžina nulinį žymeklį arba žymeklį į paskirtą erdvę.

Ir POSIX apibrėžia posix_memalign() :

 #include <stdlib.h> int posix_memalign(void **memptr, size_t alignment, size_t size); 

APRAŠYMAS

Funkcija posix_memalign() turi paskirstyti size baitus, suderintus su riba, kurią nurodo alignment , ir grąžina žymiklį į priskirtą atmintį memptr . alignment reikšmė turėtų būti dviejų daugialypių sizeof(void *) galia.

Sėkmingai atlikus vertę, memptr nurodyta vertė turi būti memptr .

Jei prašomos vietos dydis yra 0, elgesį lemia įgyvendinimas; „ memptr grąžinama vertė turi būti arba nulio rodyklė, arba unikali rodyklė.

free() funkcija turėtų atlaisvinti atmintį, anksčiau priskirtą posix_memalign() .

GRĄŽINIMO VERTĖ

Sėkmingai užbaigus, posix_memalign() grąžina nulį; priešingu atveju, norint nurodyti klaidą, reikia grąžinti klaidos numerį.

Atsakydami į klausimą dabar arba abu, arba abu gali būti naudojamasi tik POSIX funkcija, kai buvo iš pradžių atsakyta į klausimą.

Užkulisiuose, suderinta atminties funkcija atlieka tą patį darbą, kaip ir klausime, išskyrus tai, kad jie turi galimybę supaprastinti lygiavimą ir sekti suderintos atminties pradžią, kad kodą nereikėtų spręsti konkrečiai - tai paprasčiausiai išlaisvina iš platinimo funkcijos grąžinamą atmintį, kuris buvo naudojamas.

522
23 окт. Atsakymas Jonathan Leffler spalio 23 d 2008-10-23 02:27 '08, 02:27, 2008-10-23 02:27

Trys šiek tiek skirtingi atsakymai priklauso nuo to, kaip žiūrite klausimą:

1) Pakankamai gerai, kad Jonathan Leffler užduotų klausimą, išskyrus tai, kad apvalinant iki 16 kartų reikia tik 15 papildomų baitų, o ne 16.

A:

  void *mem = malloc(1024+15); ASSERT(mem); // some kind of error-handling code  void *ptr = ((char*)mem+15)  ~ (size_t)0x0F; 

Į:

 free(mem); 

2) Bendresnei atminties paskirstymo funkcijai skambinantysis nenori stebėti dviejų rodmenų (vienas naudoti ir vienas išleisti). Taigi, išsaugote žymiklį į „tikrąjį“ buferį žemiau lygio buferio.

A:

 void *mem = malloc(1024+15+sizeof(void*)); if (!mem) return mem; void *ptr = ((char*)mem+sizeof(void*)+15)  ~ (size_t)0x0F; ((void**)ptr)[-1] = mem; return ptr; 

Į:

 if (ptr) free(((void**)ptr)[-1]); 

Atkreipkite dėmesį, kad, skirtingai nei (1), kur tik 15 baitų pridedama prie mem, šis kodas iš tikrųjų gali sumažinti derinimą, jei jūsų įgyvendinimas garantuoja 32 baitų lygiavimą nuo malloc (mažai tikėtina, bet teoriškai C gali turėti 32 baitų tipo). Nesvarbu, ar viskas, ką darote, yra skambinti „memset_16“, bet jei naudosite atmintį struktūrai, tai gali reikšti.

Nesu tikras, kad tai yra geras sprendimas šiam tikslui (išskyrus įspėjimą vartotojui, kad grąžinamas buferis nebūtinai tinka savavališkoms struktūroms), nes nėra jokio būdo nustatyti programiškai, kad įgyvendinimas yra garantuotas. Manau, jei pradėjote, galite skirti du ar daugiau 1 baitų buferių ir manyti, kad blogiausias derinimas, kurį matote, yra garantuotas suderinimas. Jei klystate, prarasite atmintį. Kiekvienas, turintis geresnę idėją, pasakyk ...

[Pridėta: „standartinis“ triukas yra sukurti „tikėtiną maksimaliai suderintą tipo“ sąjungą, kad būtų galima nustatyti reikiamą derinimą. Maksimaliai suderinti tipai gali būti (C99) „ long long “, „ long double “, „ void * “ arba „ void (*)(void) “; jei įtraukėte <stdint.h> , galite naudoti „ intmax_t “ vietoj long long (ir „Power 6“ (AIX) intmax_t suteiks 128 bitų sveikojo skaičiaus tipą). Šios sąjungos derinimo reikalavimus galima nustatyti įterpiant ją į struktūrą, kurioje yra vienas žiedas, o po to - sąjunga:

 struct alignment { char c; union { intmax_t imax; long double ldbl; void *vptr; void (*fptr)(void); } u; } align_data; size_t align = (char *) - > 

Tada naudosite didesnę pageidaujamo derinimo reikšmę (pavyzdyje 16) ir aukščiau apskaičiuotą align vertę.

Solaris 10 (64 bitų) atrodo, kad pagrindinis malloc() yra 32 baitų daugiklis.
]

Praktiškai, suderinti vožtuvai dažnai turi parametrą, kad būtų suderinti, o ne griežtai sujungti. Taigi vartotojas perduos struktūros, kurią jie rūpinasi, dydį (arba mažiausia galia 2 yra didesnė arba lygi), ir visi bus gerai.

3) Naudokite, ką siūlo jūsų platforma: posix_memalign for POSIX, _aligned_malloc sistemoje „Windows“.

4) Jei naudojate C11, tada švariausia - nešiojamoji ir glausta parinktis - naudoti standartinę bibliotekos funkciją, aligned_alloc , kuri buvo įvesta šioje kalbos specifikacijos versijoje.

51
23 окт. Steve Jessop atsakymas, pateiktas spalio 23 d 2008-10-23 03:22 '08 at 3:22 am 2008-10-23 03:22

Taip pat galite pabandyti posix_memalign() (žinoma POSIX platformose).

37
23 окт. atsakymas duotas florin 23 spalis. 2008-10-23 02:36 '08, 02:36, 2008-10-23 02:36

Čia yra alternatyvus požiūris į „apvalinimo“ dalį. Ne pats ryškiausiai koduotas sprendimas, bet jis atlieka savo užduotį, ir šios rūšies sintaksė yra šiek tiek lengviau prisiminti (plius jis veiks lygiavertes reikšmes, kurių vertė nėra 2). uintptr_t buvo reikalingas kompiliatoriui nuraminti; rodyklės aritmetika nepatinka dalijimui ar dauginimui.

 void *mem = malloc(1024 + 15); void *ptr = (void*) ((uintptr_t) mem + 15) / 16 * 16; memset_16aligned(ptr, 0, 1024); free(mem); 
19
23 окт. atsakymas, pateiktas „ An̲̳̳drew“ spalio 23 d 2008-10-23 03:46 '08, 03:46, 2008-10-23 03:46

Deja, atrodo, kad C99 atveju sunku užtikrinti bet kokio tipo suderinimą tokiu būdu, kuris būtų nešiojamas bet kuriame C įgyvendinimo procese, atitinkančiame C99. Kodėl? Kadangi rodyklė negali būti „baito adresas“, kurį galima atvaizduoti naudojant modelį su plokščia atmintimi. Be to, uintptr_t atstovavimas nėra garantuotas, kuris bet kuriuo atveju yra neprivalomas.

Mes galime žinoti apie kai kurias realizacijas, kurios naudoja vaizdą negaliojančiai * (ir pagal apibrėžimą taip pat char * ), kuris yra paprastas baito adresas, bet C99 mums, programuotojams, nėra skaidrus. Įgyvendinimas gali būti rodyklė, naudojant rinkinį {segmentas, nuokrypis}, kur poslinkis gali būti kažkas, kuris žino, kad lygiavimas yra „iš tikrųjų“. Kodėl, rodyklė gali būti netgi tam tikra maišos lentelės forma arba netgi susieto sąrašo pamatinė vertė. Jis gali koduoti ribinę informaciją.

Naujausiame C standarto CX projekte matome raktinį žodį _Alignas . Tai gali šiek tiek padėti.

Vienintelė garantija, kad C99 suteikia, kad atminties priskyrimo funkcijos grąžins žymeklį, tinkantį priskirti rodyklę, nukreiptą į bet kurio tipo objektą. Kadangi negalime nurodyti objektų derinimo, negalime įgyvendinti savo paskirstymo funkcijų, atsakingų už suderinimą gerai apibrėžtame, nešiojamame režime.

Būtų malonu padaryti klaidą šiame pareiškime.

18
07 авг. atsakymas duotas Shao 07 rug. 2010-08-07 13:36 '10, 13:36, 2010-08-07 13:36

Slinkties priekyje 16, palyginti su 15 baitų, faktinis skaičius, kurį reikia pridėti norint gauti N lygiavimą, yra max (0, NM) , kur M yra natūralus atminties skirstytuvo išlygiavimas (ir abi galios yra 2).

Kadangi bet kurio skirstytuvo minimalus atminties lygiavimas yra 1 baitas, 15 = max (0.16-1) yra konservatyvus atsakymas. Tačiau, jei žinote, kad jūsų atminties skirstytuvas suteiks jums 32 bitų int-align adresus (kurie yra gana dažni), galite naudoti 12 kaip trinkelę.

Tai nėra svarbu šiame pavyzdyje, tačiau ji gali būti svarbi įterptinėje sistemoje su 12 KB RAM, kurioje apskaičiuojama kiekviena išsaugota sąskaita.

Geriausias būdas jį įgyvendinti, jei ketinate pabandyti išsaugoti kiekvieną baitą, yra makrokomandas, kad galėtumėte ją koreguoti. Vėlgi, tai tikriausiai naudinga tik įterptoms sistemoms, kuriose reikia išsaugoti kiekvieną baitą.

Toliau pateiktame pavyzdyje, daugumoje sistemų, 1 reikšmė puikiai tinka MEMORY_ALLOCATOR_NATIVE_ALIGNMENT , tačiau mūsų teorinėje įterptinėje sistemoje su 32 bitų suderintomis parinktimis, šie veiksmai gali sutaupyti nedidelę vertingą atmintį:

 #define MEMORY_ALLOCATOR_NATIVE_ALIGNMENT 4 #define ALIGN_PAD2(N,M) (((N)>(M)) ? ((N)-(M)) : 0) #define ALIGN_PAD(N) ALIGN_PAD2((N), MEMORY_ALLOCATOR_NATIVE_ALIGNMENT) 
14
21 окт. Atsakymą Adisak pateikė spalio 21 d. 2009-10-21 19:40 '09, 07:40 pm 2009-10-21 19:40

Galbūt jie būtų patenkinti atminties žiniomis? Ir, kaip nurodo Jonathan Leffler, yra dvi naujos pageidaujamos funkcijos, kurias galite sužinoti.

Oi, Florinas mušė mane. Tačiau, jei perskaitėte pagalbos puslapį, su kuriuo esu prijungtas, greičiausiai suprasite ankstesnio plakato pateiktą pavyzdį.

8
23 окт. Don Wakefield atsakymas spalio 23 d 2008-10-23 02:42 '08, 02:42 am 2008-10-23 02:42

Esu nustebęs, kad niekas balsavo „ Shao“, kad atsakytų, jog, kaip suprantu, neįmanoma padaryti to, kas nurodyta C99 standarte, nes oficiali rodyklės konversija į vientisą tipą yra neapibrėžta. (Be standarto, leidžiančio konvertuoti uintptr_tvoid* , tačiau standartas, atrodo, neleidžia manipuliuoti vertėmis uintptr_t ir tada jį konvertuoti atgal.)

5
14 июля '11 в 19:34 2011-07-14 19:34 atsakymą pateikė Lutorm, liepos 14 d., 11 val., 19:34, 2011-07-14 19:34

Mes visą laiką atliekame Accelerate.framework, labai vektorizuotą OS X / iOS biblioteką, kur turime nuolat atkreipti dėmesį į derinimą. Существует несколько вариантов, один или два из которых я не видел выше.