futex.c 71 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741
  1. /*
  2. * Fast Userspace Mutexes (which I call "Futexes!").
  3. * (C) Rusty Russell, IBM 2002
  4. *
  5. * Generalized futexes, futex requeueing, misc fixes by Ingo Molnar
  6. * (C) Copyright 2003 Red Hat Inc, All Rights Reserved
  7. *
  8. * Removed page pinning, fix privately mapped COW pages and other cleanups
  9. * (C) Copyright 2003, 2004 Jamie Lokier
  10. *
  11. * Robust futex support started by Ingo Molnar
  12. * (C) Copyright 2006 Red Hat Inc, All Rights Reserved
  13. * Thanks to Thomas Gleixner for suggestions, analysis and fixes.
  14. *
  15. * PI-futex support started by Ingo Molnar and Thomas Gleixner
  16. * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
  17. * Copyright (C) 2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
  18. *
  19. * PRIVATE futexes by Eric Dumazet
  20. * Copyright (C) 2007 Eric Dumazet <dada1@cosmosbay.com>
  21. *
  22. * Requeue-PI support by Darren Hart <dvhltc@us.ibm.com>
  23. * Copyright (C) IBM Corporation, 2009
  24. * Thanks to Thomas Gleixner for conceptual design and careful reviews.
  25. *
  26. * Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
  27. * enough at me, Linus for the original (flawed) idea, Matthew
  28. * Kirkwood for proof-of-concept implementation.
  29. *
  30. * "The futexes are also cursed."
  31. * "But they come in a choice of three flavours!"
  32. *
  33. * This program is free software; you can redistribute it and/or modify
  34. * it under the terms of the GNU General Public License as published by
  35. * the Free Software Foundation; either version 2 of the License, or
  36. * (at your option) any later version.
  37. *
  38. * This program is distributed in the hope that it will be useful,
  39. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  40. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  41. * GNU General Public License for more details.
  42. *
  43. * You should have received a copy of the GNU General Public License
  44. * along with this program; if not, write to the Free Software
  45. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  46. */
  47. #include <linux/slab.h>
  48. #include <linux/poll.h>
  49. #include <linux/fs.h>
  50. #include <linux/file.h>
  51. #include <linux/jhash.h>
  52. #include <linux/init.h>
  53. #include <linux/futex.h>
  54. #include <linux/mount.h>
  55. #include <linux/pagemap.h>
  56. #include <linux/syscalls.h>
  57. #include <linux/signal.h>
  58. #include <linux/export.h>
  59. #include <linux/magic.h>
  60. #include <linux/pid.h>
  61. #include <linux/nsproxy.h>
  62. #include <linux/ptrace.h>
  63. #include <asm/futex.h>
  64. #include "rtmutex_common.h"
  65. int __read_mostly futex_cmpxchg_enabled;
  66. #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
  67. /*
  68. * Futex flags used to encode options to functions and preserve them across
  69. * restarts.
  70. */
  71. #define FLAGS_SHARED 0x01
  72. #define FLAGS_CLOCKRT 0x02
  73. #define FLAGS_HAS_TIMEOUT 0x04
  74. /*
  75. * Priority Inheritance state:
  76. */
  77. struct futex_pi_state {
  78. /*
  79. * list of 'owned' pi_state instances - these have to be
  80. * cleaned up in do_exit() if the task exits prematurely:
  81. */
  82. struct list_head list;
  83. /*
  84. * The PI object:
  85. */
  86. struct rt_mutex pi_mutex;
  87. struct task_struct *owner;
  88. atomic_t refcount;
  89. union futex_key key;
  90. };
  91. /**
  92. * struct futex_q - The hashed futex queue entry, one per waiting task
  93. * @list: priority-sorted list of tasks waiting on this futex
  94. * @task: the task waiting on the futex
  95. * @lock_ptr: the hash bucket lock
  96. * @key: the key the futex is hashed on
  97. * @pi_state: optional priority inheritance state
  98. * @rt_waiter: rt_waiter storage for use with requeue_pi
  99. * @requeue_pi_key: the requeue_pi target futex key
  100. * @bitset: bitset for the optional bitmasked wakeup
  101. *
  102. * We use this hashed waitqueue, instead of a normal wait_queue_t, so
  103. * we can wake only the relevant ones (hashed queues may be shared).
  104. *
  105. * A futex_q has a woken state, just like tasks have TASK_RUNNING.
  106. * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
  107. * The order of wakeup is always to make the first condition true, then
  108. * the second.
  109. *
  110. * PI futexes are typically woken before they are removed from the hash list via
  111. * the rt_mutex code. See unqueue_me_pi().
  112. */
  113. struct futex_q {
  114. struct plist_node list;
  115. struct task_struct *task;
  116. spinlock_t *lock_ptr;
  117. union futex_key key;
  118. struct futex_pi_state *pi_state;
  119. struct rt_mutex_waiter *rt_waiter;
  120. union futex_key *requeue_pi_key;
  121. u32 bitset;
  122. };
  123. static const struct futex_q futex_q_init = {
  124. /* list gets initialized in queue_me()*/
  125. .key = FUTEX_KEY_INIT,
  126. .bitset = FUTEX_BITSET_MATCH_ANY
  127. };
  128. /*
  129. * Hash buckets are shared by all the futex_keys that hash to the same
  130. * location. Each key may have multiple futex_q structures, one for each task
  131. * waiting on a futex.
  132. */
  133. struct futex_hash_bucket {
  134. spinlock_t lock;
  135. struct plist_head chain;
  136. };
  137. static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
  138. /*
  139. * We hash on the keys returned from get_futex_key (see below).
  140. */
  141. static struct futex_hash_bucket *hash_futex(union futex_key *key)
  142. {
  143. u32 hash = jhash2((u32*)&key->both.word,
  144. (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
  145. key->both.offset);
  146. return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
  147. }
  148. /*
  149. * Return 1 if two futex_keys are equal, 0 otherwise.
  150. */
  151. static inline int match_futex(union futex_key *key1, union futex_key *key2)
  152. {
  153. return (key1 && key2
  154. && key1->both.word == key2->both.word
  155. && key1->both.ptr == key2->both.ptr
  156. && key1->both.offset == key2->both.offset);
  157. }
  158. /*
  159. * Take a reference to the resource addressed by a key.
  160. * Can be called while holding spinlocks.
  161. *
  162. */
  163. static void get_futex_key_refs(union futex_key *key)
  164. {
  165. if (!key->both.ptr)
  166. return;
  167. switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
  168. case FUT_OFF_INODE:
  169. ihold(key->shared.inode);
  170. break;
  171. case FUT_OFF_MMSHARED:
  172. atomic_inc(&key->private.mm->mm_count);
  173. break;
  174. }
  175. }
  176. /*
  177. * Drop a reference to the resource addressed by a key.
  178. * The hash bucket spinlock must not be held.
  179. */
  180. static void drop_futex_key_refs(union futex_key *key)
  181. {
  182. if (!key->both.ptr) {
  183. /* If we're here then we tried to put a key we failed to get */
  184. WARN_ON_ONCE(1);
  185. return;
  186. }
  187. switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
  188. case FUT_OFF_INODE:
  189. iput(key->shared.inode);
  190. break;
  191. case FUT_OFF_MMSHARED:
  192. mmdrop(key->private.mm);
  193. break;
  194. }
  195. }
  196. /**
  197. * get_futex_key() - Get parameters which are the keys for a futex
  198. * @uaddr: virtual address of the futex
  199. * @fshared: 0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED
  200. * @key: address where result is stored.
  201. * @rw: mapping needs to be read/write (values: VERIFY_READ,
  202. * VERIFY_WRITE)
  203. *
  204. * Returns a negative error code or 0
  205. * The key words are stored in *key on success.
  206. *
  207. * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode,
  208. * offset_within_page). For private mappings, it's (uaddr, current->mm).
  209. * We can usually work out the index without swapping in the page.
  210. *
  211. * lock_page() might sleep, the caller should not hold a spinlock.
  212. */
  213. static int
  214. get_futex_key(u32 __user *uaddr, int fshared, union futex_key *key, int rw)
  215. {
  216. unsigned long address = (unsigned long)uaddr;
  217. struct mm_struct *mm = current->mm;
  218. struct page *page, *page_head;
  219. int err, ro = 0;
  220. /*
  221. * The futex address must be "naturally" aligned.
  222. */
  223. key->both.offset = address % PAGE_SIZE;
  224. if (unlikely((address % sizeof(u32)) != 0))
  225. return -EINVAL;
  226. address -= key->both.offset;
  227. /*
  228. * PROCESS_PRIVATE futexes are fast.
  229. * As the mm cannot disappear under us and the 'key' only needs
  230. * virtual address, we dont even have to find the underlying vma.
  231. * Note : We do have to check 'uaddr' is a valid user address,
  232. * but access_ok() should be faster than find_vma()
  233. */
  234. if (!fshared) {
  235. if (unlikely(!access_ok(VERIFY_WRITE, uaddr, sizeof(u32))))
  236. return -EFAULT;
  237. key->private.mm = mm;
  238. key->private.address = address;
  239. get_futex_key_refs(key);
  240. return 0;
  241. }
  242. again:
  243. err = get_user_pages_fast(address, 1, 1, &page);
  244. /*
  245. * If write access is not required (eg. FUTEX_WAIT), try
  246. * and get read-only access.
  247. */
  248. if (err == -EFAULT && rw == VERIFY_READ) {
  249. err = get_user_pages_fast(address, 1, 0, &page);
  250. ro = 1;
  251. }
  252. if (err < 0)
  253. return err;
  254. else
  255. err = 0;
  256. #ifdef CONFIG_TRANSPARENT_HUGEPAGE
  257. page_head = page;
  258. if (unlikely(PageTail(page))) {
  259. put_page(page);
  260. /* serialize against __split_huge_page_splitting() */
  261. local_irq_disable();
  262. if (likely(__get_user_pages_fast(address, 1, 1, &page) == 1)) {
  263. page_head = compound_head(page);
  264. /*
  265. * page_head is valid pointer but we must pin
  266. * it before taking the PG_lock and/or
  267. * PG_compound_lock. The moment we re-enable
  268. * irqs __split_huge_page_splitting() can
  269. * return and the head page can be freed from
  270. * under us. We can't take the PG_lock and/or
  271. * PG_compound_lock on a page that could be
  272. * freed from under us.
  273. */
  274. if (page != page_head) {
  275. get_page(page_head);
  276. put_page(page);
  277. }
  278. local_irq_enable();
  279. } else {
  280. local_irq_enable();
  281. goto again;
  282. }
  283. }
  284. #else
  285. page_head = compound_head(page);
  286. if (page != page_head) {
  287. get_page(page_head);
  288. put_page(page);
  289. }
  290. #endif
  291. lock_page(page_head);
  292. /*
  293. * If page_head->mapping is NULL, then it cannot be a PageAnon
  294. * page; but it might be the ZERO_PAGE or in the gate area or
  295. * in a special mapping (all cases which we are happy to fail);
  296. * or it may have been a good file page when get_user_pages_fast
  297. * found it, but truncated or holepunched or subjected to
  298. * invalidate_complete_page2 before we got the page lock (also
  299. * cases which we are happy to fail). And we hold a reference,
  300. * so refcount care in invalidate_complete_page's remove_mapping
  301. * prevents drop_caches from setting mapping to NULL beneath us.
  302. *
  303. * The case we do have to guard against is when memory pressure made
  304. * shmem_writepage move it from filecache to swapcache beneath us:
  305. * an unlikely race, but we do need to retry for page_head->mapping.
  306. */
  307. if (!page_head->mapping) {
  308. int shmem_swizzled = PageSwapCache(page_head);
  309. unlock_page(page_head);
  310. put_page(page_head);
  311. if (shmem_swizzled)
  312. goto again;
  313. return -EFAULT;
  314. }
  315. /*
  316. * Private mappings are handled in a simple way.
  317. *
  318. * NOTE: When userspace waits on a MAP_SHARED mapping, even if
  319. * it's a read-only handle, it's expected that futexes attach to
  320. * the object not the particular process.
  321. */
  322. if (PageAnon(page_head)) {
  323. /*
  324. * A RO anonymous page will never change and thus doesn't make
  325. * sense for futex operations.
  326. */
  327. if (ro) {
  328. err = -EFAULT;
  329. goto out;
  330. }
  331. key->both.offset |= FUT_OFF_MMSHARED; /* ref taken on mm */
  332. key->private.mm = mm;
  333. key->private.address = address;
  334. } else {
  335. key->both.offset |= FUT_OFF_INODE; /* inode-based key */
  336. key->shared.inode = page_head->mapping->host;
  337. key->shared.pgoff = page_head->index;
  338. }
  339. get_futex_key_refs(key);
  340. out:
  341. unlock_page(page_head);
  342. put_page(page_head);
  343. return err;
  344. }
  345. static inline void put_futex_key(union futex_key *key)
  346. {
  347. drop_futex_key_refs(key);
  348. }
  349. /**
  350. * fault_in_user_writeable() - Fault in user address and verify RW access
  351. * @uaddr: pointer to faulting user space address
  352. *
  353. * Slow path to fixup the fault we just took in the atomic write
  354. * access to @uaddr.
  355. *
  356. * We have no generic implementation of a non-destructive write to the
  357. * user address. We know that we faulted in the atomic pagefault
  358. * disabled section so we can as well avoid the #PF overhead by
  359. * calling get_user_pages() right away.
  360. */
  361. static int fault_in_user_writeable(u32 __user *uaddr)
  362. {
  363. struct mm_struct *mm = current->mm;
  364. int ret;
  365. down_read(&mm->mmap_sem);
  366. ret = fixup_user_fault(current, mm, (unsigned long)uaddr,
  367. FAULT_FLAG_WRITE);
  368. up_read(&mm->mmap_sem);
  369. return ret < 0 ? ret : 0;
  370. }
  371. /**
  372. * futex_top_waiter() - Return the highest priority waiter on a futex
  373. * @hb: the hash bucket the futex_q's reside in
  374. * @key: the futex key (to distinguish it from other futex futex_q's)
  375. *
  376. * Must be called with the hb lock held.
  377. */
  378. static struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb,
  379. union futex_key *key)
  380. {
  381. struct futex_q *this;
  382. plist_for_each_entry(this, &hb->chain, list) {
  383. if (match_futex(&this->key, key))
  384. return this;
  385. }
  386. return NULL;
  387. }
  388. static int cmpxchg_futex_value_locked(u32 *curval, u32 __user *uaddr,
  389. u32 uval, u32 newval)
  390. {
  391. int ret;
  392. pagefault_disable();
  393. ret = futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);
  394. pagefault_enable();
  395. return ret;
  396. }
  397. static int get_futex_value_locked(u32 *dest, u32 __user *from)
  398. {
  399. int ret;
  400. pagefault_disable();
  401. ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
  402. pagefault_enable();
  403. return ret ? -EFAULT : 0;
  404. }
  405. /*
  406. * PI code:
  407. */
  408. static int refill_pi_state_cache(void)
  409. {
  410. struct futex_pi_state *pi_state;
  411. if (likely(current->pi_state_cache))
  412. return 0;
  413. pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
  414. if (!pi_state)
  415. return -ENOMEM;
  416. INIT_LIST_HEAD(&pi_state->list);
  417. /* pi_mutex gets initialized later */
  418. pi_state->owner = NULL;
  419. atomic_set(&pi_state->refcount, 1);
  420. pi_state->key = FUTEX_KEY_INIT;
  421. current->pi_state_cache = pi_state;
  422. return 0;
  423. }
  424. static struct futex_pi_state * alloc_pi_state(void)
  425. {
  426. struct futex_pi_state *pi_state = current->pi_state_cache;
  427. WARN_ON(!pi_state);
  428. current->pi_state_cache = NULL;
  429. return pi_state;
  430. }
  431. static void free_pi_state(struct futex_pi_state *pi_state)
  432. {
  433. if (!atomic_dec_and_test(&pi_state->refcount))
  434. return;
  435. /*
  436. * If pi_state->owner is NULL, the owner is most probably dying
  437. * and has cleaned up the pi_state already
  438. */
  439. if (pi_state->owner) {
  440. raw_spin_lock_irq(&pi_state->owner->pi_lock);
  441. list_del_init(&pi_state->list);
  442. raw_spin_unlock_irq(&pi_state->owner->pi_lock);
  443. rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
  444. }
  445. if (current->pi_state_cache)
  446. kfree(pi_state);
  447. else {
  448. /*
  449. * pi_state->list is already empty.
  450. * clear pi_state->owner.
  451. * refcount is at 0 - put it back to 1.
  452. */
  453. pi_state->owner = NULL;
  454. atomic_set(&pi_state->refcount, 1);
  455. current->pi_state_cache = pi_state;
  456. }
  457. }
  458. /*
  459. * Look up the task based on what TID userspace gave us.
  460. * We dont trust it.
  461. */
  462. static struct task_struct * futex_find_get_task(pid_t pid)
  463. {
  464. struct task_struct *p;
  465. rcu_read_lock();
  466. p = find_task_by_vpid(pid);
  467. if (p)
  468. get_task_struct(p);
  469. rcu_read_unlock();
  470. return p;
  471. }
  472. /*
  473. * This task is holding PI mutexes at exit time => bad.
  474. * Kernel cleans up PI-state, but userspace is likely hosed.
  475. * (Robust-futex cleanup is separate and might save the day for userspace.)
  476. */
  477. void exit_pi_state_list(struct task_struct *curr)
  478. {
  479. struct list_head *next, *head = &curr->pi_state_list;
  480. struct futex_pi_state *pi_state;
  481. struct futex_hash_bucket *hb;
  482. union futex_key key = FUTEX_KEY_INIT;
  483. if (!futex_cmpxchg_enabled)
  484. return;
  485. /*
  486. * We are a ZOMBIE and nobody can enqueue itself on
  487. * pi_state_list anymore, but we have to be careful
  488. * versus waiters unqueueing themselves:
  489. */
  490. raw_spin_lock_irq(&curr->pi_lock);
  491. while (!list_empty(head)) {
  492. next = head->next;
  493. pi_state = list_entry(next, struct futex_pi_state, list);
  494. key = pi_state->key;
  495. hb = hash_futex(&key);
  496. raw_spin_unlock_irq(&curr->pi_lock);
  497. spin_lock(&hb->lock);
  498. raw_spin_lock_irq(&curr->pi_lock);
  499. /*
  500. * We dropped the pi-lock, so re-check whether this
  501. * task still owns the PI-state:
  502. */
  503. if (head->next != next) {
  504. spin_unlock(&hb->lock);
  505. continue;
  506. }
  507. WARN_ON(pi_state->owner != curr);
  508. WARN_ON(list_empty(&pi_state->list));
  509. list_del_init(&pi_state->list);
  510. pi_state->owner = NULL;
  511. raw_spin_unlock_irq(&curr->pi_lock);
  512. rt_mutex_unlock(&pi_state->pi_mutex);
  513. spin_unlock(&hb->lock);
  514. raw_spin_lock_irq(&curr->pi_lock);
  515. }
  516. raw_spin_unlock_irq(&curr->pi_lock);
  517. }
  518. static int
  519. lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
  520. union futex_key *key, struct futex_pi_state **ps)
  521. {
  522. struct futex_pi_state *pi_state = NULL;
  523. struct futex_q *this, *next;
  524. struct plist_head *head;
  525. struct task_struct *p;
  526. pid_t pid = uval & FUTEX_TID_MASK;
  527. head = &hb->chain;
  528. plist_for_each_entry_safe(this, next, head, list) {
  529. if (match_futex(&this->key, key)) {
  530. /*
  531. * Another waiter already exists - bump up
  532. * the refcount and return its pi_state:
  533. */
  534. pi_state = this->pi_state;
  535. /*
  536. * Userspace might have messed up non-PI and PI futexes
  537. */
  538. if (unlikely(!pi_state))
  539. return -EINVAL;
  540. WARN_ON(!atomic_read(&pi_state->refcount));
  541. /*
  542. * When pi_state->owner is NULL then the owner died
  543. * and another waiter is on the fly. pi_state->owner
  544. * is fixed up by the task which acquires
  545. * pi_state->rt_mutex.
  546. *
  547. * We do not check for pid == 0 which can happen when
  548. * the owner died and robust_list_exit() cleared the
  549. * TID.
  550. */
  551. if (pid && pi_state->owner) {
  552. /*
  553. * Bail out if user space manipulated the
  554. * futex value.
  555. */
  556. if (pid != task_pid_vnr(pi_state->owner))
  557. return -EINVAL;
  558. }
  559. atomic_inc(&pi_state->refcount);
  560. *ps = pi_state;
  561. return 0;
  562. }
  563. }
  564. /*
  565. * We are the first waiter - try to look up the real owner and attach
  566. * the new pi_state to it, but bail out when TID = 0
  567. */
  568. if (!pid)
  569. return -ESRCH;
  570. p = futex_find_get_task(pid);
  571. if (!p)
  572. return -ESRCH;
  573. /*
  574. * We need to look at the task state flags to figure out,
  575. * whether the task is exiting. To protect against the do_exit
  576. * change of the task flags, we do this protected by
  577. * p->pi_lock:
  578. */
  579. raw_spin_lock_irq(&p->pi_lock);
  580. if (unlikely(p->flags & PF_EXITING)) {
  581. /*
  582. * The task is on the way out. When PF_EXITPIDONE is
  583. * set, we know that the task has finished the
  584. * cleanup:
  585. */
  586. int ret = (p->flags & PF_EXITPIDONE) ? -ESRCH : -EAGAIN;
  587. raw_spin_unlock_irq(&p->pi_lock);
  588. put_task_struct(p);
  589. return ret;
  590. }
  591. pi_state = alloc_pi_state();
  592. /*
  593. * Initialize the pi_mutex in locked state and make 'p'
  594. * the owner of it:
  595. */
  596. rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
  597. /* Store the key for possible exit cleanups: */
  598. pi_state->key = *key;
  599. WARN_ON(!list_empty(&pi_state->list));
  600. list_add(&pi_state->list, &p->pi_state_list);
  601. pi_state->owner = p;
  602. raw_spin_unlock_irq(&p->pi_lock);
  603. put_task_struct(p);
  604. *ps = pi_state;
  605. return 0;
  606. }
  607. /**
  608. * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
  609. * @uaddr: the pi futex user address
  610. * @hb: the pi futex hash bucket
  611. * @key: the futex key associated with uaddr and hb
  612. * @ps: the pi_state pointer where we store the result of the
  613. * lookup
  614. * @task: the task to perform the atomic lock work for. This will
  615. * be "current" except in the case of requeue pi.
  616. * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
  617. *
  618. * Returns:
  619. * 0 - ready to wait
  620. * 1 - acquired the lock
  621. * <0 - error
  622. *
  623. * The hb->lock and futex_key refs shall be held by the caller.
  624. */
  625. static int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
  626. union futex_key *key,
  627. struct futex_pi_state **ps,
  628. struct task_struct *task, int set_waiters)
  629. {
  630. int lock_taken, ret, force_take = 0;
  631. u32 uval, newval, curval, vpid = task_pid_vnr(task);
  632. retry:
  633. ret = lock_taken = 0;
  634. /*
  635. * To avoid races, we attempt to take the lock here again
  636. * (by doing a 0 -> TID atomic cmpxchg), while holding all
  637. * the locks. It will most likely not succeed.
  638. */
  639. newval = vpid;
  640. if (set_waiters)
  641. newval |= FUTEX_WAITERS;
  642. if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, 0, newval)))
  643. return -EFAULT;
  644. /*
  645. * Detect deadlocks.
  646. */
  647. if ((unlikely((curval & FUTEX_TID_MASK) == vpid)))
  648. return -EDEADLK;
  649. /*
  650. * Surprise - we got the lock. Just return to userspace:
  651. */
  652. if (unlikely(!curval))
  653. return 1;
  654. uval = curval;
  655. /*
  656. * Set the FUTEX_WAITERS flag, so the owner will know it has someone
  657. * to wake at the next unlock.
  658. */
  659. newval = curval | FUTEX_WAITERS;
  660. /*
  661. * Should we force take the futex? See below.
  662. */
  663. if (unlikely(force_take)) {
  664. /*
  665. * Keep the OWNER_DIED and the WAITERS bit and set the
  666. * new TID value.
  667. */
  668. newval = (curval & ~FUTEX_TID_MASK) | vpid;
  669. force_take = 0;
  670. lock_taken = 1;
  671. }
  672. if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)))
  673. return -EFAULT;
  674. if (unlikely(curval != uval))
  675. goto retry;
  676. /*
  677. * We took the lock due to forced take over.
  678. */
  679. if (unlikely(lock_taken))
  680. return 1;
  681. /*
  682. * We dont have the lock. Look up the PI state (or create it if
  683. * we are the first waiter):
  684. */
  685. ret = lookup_pi_state(uval, hb, key, ps);
  686. if (unlikely(ret)) {
  687. switch (ret) {
  688. case -ESRCH:
  689. /*
  690. * We failed to find an owner for this
  691. * futex. So we have no pi_state to block
  692. * on. This can happen in two cases:
  693. *
  694. * 1) The owner died
  695. * 2) A stale FUTEX_WAITERS bit
  696. *
  697. * Re-read the futex value.
  698. */
  699. if (get_futex_value_locked(&curval, uaddr))
  700. return -EFAULT;
  701. /*
  702. * If the owner died or we have a stale
  703. * WAITERS bit the owner TID in the user space
  704. * futex is 0.
  705. */
  706. if (!(curval & FUTEX_TID_MASK)) {
  707. force_take = 1;
  708. goto retry;
  709. }
  710. default:
  711. break;
  712. }
  713. }
  714. return ret;
  715. }
  716. /**
  717. * __unqueue_futex() - Remove the futex_q from its futex_hash_bucket
  718. * @q: The futex_q to unqueue
  719. *
  720. * The q->lock_ptr must not be NULL and must be held by the caller.
  721. */
  722. static void __unqueue_futex(struct futex_q *q)
  723. {
  724. struct futex_hash_bucket *hb;
  725. if (WARN_ON_SMP(!q->lock_ptr || !spin_is_locked(q->lock_ptr))
  726. || WARN_ON(plist_node_empty(&q->list)))
  727. return;
  728. hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);
  729. plist_del(&q->list, &hb->chain);
  730. }
  731. /*
  732. * The hash bucket lock must be held when this is called.
  733. * Afterwards, the futex_q must not be accessed.
  734. */
  735. static void wake_futex(struct futex_q *q)
  736. {
  737. struct task_struct *p = q->task;
  738. /*
  739. * We set q->lock_ptr = NULL _before_ we wake up the task. If
  740. * a non-futex wake up happens on another CPU then the task
  741. * might exit and p would dereference a non-existing task
  742. * struct. Prevent this by holding a reference on p across the
  743. * wake up.
  744. */
  745. get_task_struct(p);
  746. __unqueue_futex(q);
  747. /*
  748. * The waiting task can free the futex_q as soon as
  749. * q->lock_ptr = NULL is written, without taking any locks. A
  750. * memory barrier is required here to prevent the following
  751. * store to lock_ptr from getting ahead of the plist_del.
  752. */
  753. smp_wmb();
  754. q->lock_ptr = NULL;
  755. wake_up_state(p, TASK_NORMAL);
  756. put_task_struct(p);
  757. }
  758. static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
  759. {
  760. struct task_struct *new_owner;
  761. struct futex_pi_state *pi_state = this->pi_state;
  762. u32 uninitialized_var(curval), newval;
  763. if (!pi_state)
  764. return -EINVAL;
  765. /*
  766. * If current does not own the pi_state then the futex is
  767. * inconsistent and user space fiddled with the futex value.
  768. */
  769. if (pi_state->owner != current)
  770. return -EINVAL;
  771. raw_spin_lock(&pi_state->pi_mutex.wait_lock);
  772. new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
  773. /*
  774. * It is possible that the next waiter (the one that brought
  775. * this owner to the kernel) timed out and is no longer
  776. * waiting on the lock.
  777. */
  778. if (!new_owner)
  779. new_owner = this->task;
  780. /*
  781. * We pass it to the next owner. (The WAITERS bit is always
  782. * kept enabled while there is PI state around. We must also
  783. * preserve the owner died bit.)
  784. */
  785. if (!(uval & FUTEX_OWNER_DIED)) {
  786. int ret = 0;
  787. newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
  788. if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval))
  789. ret = -EFAULT;
  790. else if (curval != uval)
  791. ret = -EINVAL;
  792. if (ret) {
  793. raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
  794. return ret;
  795. }
  796. }
  797. raw_spin_lock_irq(&pi_state->owner->pi_lock);
  798. WARN_ON(list_empty(&pi_state->list));
  799. list_del_init(&pi_state->list);
  800. raw_spin_unlock_irq(&pi_state->owner->pi_lock);
  801. raw_spin_lock_irq(&new_owner->pi_lock);
  802. WARN_ON(!list_empty(&pi_state->list));
  803. list_add(&pi_state->list, &new_owner->pi_state_list);
  804. pi_state->owner = new_owner;
  805. raw_spin_unlock_irq(&new_owner->pi_lock);
  806. raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
  807. rt_mutex_unlock(&pi_state->pi_mutex);
  808. return 0;
  809. }
  810. static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
  811. {
  812. u32 uninitialized_var(oldval);
  813. /*
  814. * There is no waiter, so we unlock the futex. The owner died
  815. * bit has not to be preserved here. We are the owner:
  816. */
  817. if (cmpxchg_futex_value_locked(&oldval, uaddr, uval, 0))
  818. return -EFAULT;
  819. if (oldval != uval)
  820. return -EAGAIN;
  821. return 0;
  822. }
  823. /*
  824. * Express the locking dependencies for lockdep:
  825. */
  826. static inline void
  827. double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
  828. {
  829. if (hb1 <= hb2) {
  830. spin_lock(&hb1->lock);
  831. if (hb1 < hb2)
  832. spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
  833. } else { /* hb1 > hb2 */
  834. spin_lock(&hb2->lock);
  835. spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
  836. }
  837. }
  838. static inline void
  839. double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
  840. {
  841. spin_unlock(&hb1->lock);
  842. if (hb1 != hb2)
  843. spin_unlock(&hb2->lock);
  844. }
  845. /*
  846. * Wake up waiters matching bitset queued on this futex (uaddr).
  847. */
  848. static int
  849. futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
  850. {
  851. struct futex_hash_bucket *hb;
  852. struct futex_q *this, *next;
  853. struct plist_head *head;
  854. union futex_key key = FUTEX_KEY_INIT;
  855. int ret;
  856. if (!bitset)
  857. return -EINVAL;
  858. ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, VERIFY_READ);
  859. if (unlikely(ret != 0))
  860. goto out;
  861. hb = hash_futex(&key);
  862. spin_lock(&hb->lock);
  863. head = &hb->chain;
  864. plist_for_each_entry_safe(this, next, head, list) {
  865. if (match_futex (&this->key, &key)) {
  866. if (this->pi_state || this->rt_waiter) {
  867. ret = -EINVAL;
  868. break;
  869. }
  870. /* Check if one of the bits is set in both bitsets */
  871. if (!(this->bitset & bitset))
  872. continue;
  873. wake_futex(this);
  874. if (++ret >= nr_wake)
  875. break;
  876. }
  877. }
  878. spin_unlock(&hb->lock);
  879. put_futex_key(&key);
  880. out:
  881. return ret;
  882. }
  883. /*
  884. * Wake up all waiters hashed on the physical page that is mapped
  885. * to this virtual address:
  886. */
  887. static int
  888. futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
  889. int nr_wake, int nr_wake2, int op)
  890. {
  891. union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
  892. struct futex_hash_bucket *hb1, *hb2;
  893. struct plist_head *head;
  894. struct futex_q *this, *next;
  895. int ret, op_ret;
  896. retry:
  897. ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, VERIFY_READ);
  898. if (unlikely(ret != 0))
  899. goto out;
  900. ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, VERIFY_WRITE);
  901. if (unlikely(ret != 0))
  902. goto out_put_key1;
  903. hb1 = hash_futex(&key1);
  904. hb2 = hash_futex(&key2);
  905. retry_private:
  906. double_lock_hb(hb1, hb2);
  907. op_ret = futex_atomic_op_inuser(op, uaddr2);
  908. if (unlikely(op_ret < 0)) {
  909. double_unlock_hb(hb1, hb2);
  910. #ifndef CONFIG_MMU
  911. /*
  912. * we don't get EFAULT from MMU faults if we don't have an MMU,
  913. * but we might get them from range checking
  914. */
  915. ret = op_ret;
  916. goto out_put_keys;
  917. #endif
  918. if (unlikely(op_ret != -EFAULT)) {
  919. ret = op_ret;
  920. goto out_put_keys;
  921. }
  922. ret = fault_in_user_writeable(uaddr2);
  923. if (ret)
  924. goto out_put_keys;
  925. if (!(flags & FLAGS_SHARED))
  926. goto retry_private;
  927. put_futex_key(&key2);
  928. put_futex_key(&key1);
  929. goto retry;
  930. }
  931. head = &hb1->chain;
  932. plist_for_each_entry_safe(this, next, head, list) {
  933. if (match_futex (&this->key, &key1)) {
  934. wake_futex(this);
  935. if (++ret >= nr_wake)
  936. break;
  937. }
  938. }
  939. if (op_ret > 0) {
  940. head = &hb2->chain;
  941. op_ret = 0;
  942. plist_for_each_entry_safe(this, next, head, list) {
  943. if (match_futex (&this->key, &key2)) {
  944. wake_futex(this);
  945. if (++op_ret >= nr_wake2)
  946. break;
  947. }
  948. }
  949. ret += op_ret;
  950. }
  951. double_unlock_hb(hb1, hb2);
  952. out_put_keys:
  953. put_futex_key(&key2);
  954. out_put_key1:
  955. put_futex_key(&key1);
  956. out:
  957. return ret;
  958. }
  959. /**
  960. * requeue_futex() - Requeue a futex_q from one hb to another
  961. * @q: the futex_q to requeue
  962. * @hb1: the source hash_bucket
  963. * @hb2: the target hash_bucket
  964. * @key2: the new key for the requeued futex_q
  965. */
  966. static inline
  967. void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
  968. struct futex_hash_bucket *hb2, union futex_key *key2)
  969. {
  970. /*
  971. * If key1 and key2 hash to the same bucket, no need to
  972. * requeue.
  973. */
  974. if (likely(&hb1->chain != &hb2->chain)) {
  975. plist_del(&q->list, &hb1->chain);
  976. plist_add(&q->list, &hb2->chain);
  977. q->lock_ptr = &hb2->lock;
  978. }
  979. get_futex_key_refs(key2);
  980. q->key = *key2;
  981. }
  982. /**
  983. * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
  984. * @q: the futex_q
  985. * @key: the key of the requeue target futex
  986. * @hb: the hash_bucket of the requeue target futex
  987. *
  988. * During futex_requeue, with requeue_pi=1, it is possible to acquire the
  989. * target futex if it is uncontended or via a lock steal. Set the futex_q key
  990. * to the requeue target futex so the waiter can detect the wakeup on the right
  991. * futex, but remove it from the hb and NULL the rt_waiter so it can detect
  992. * atomic lock acquisition. Set the q->lock_ptr to the requeue target hb->lock
  993. * to protect access to the pi_state to fixup the owner later. Must be called
  994. * with both q->lock_ptr and hb->lock held.
  995. */
  996. static inline
  997. void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
  998. struct futex_hash_bucket *hb)
  999. {
  1000. get_futex_key_refs(key);
  1001. q->key = *key;
  1002. __unqueue_futex(q);
  1003. WARN_ON(!q->rt_waiter);
  1004. q->rt_waiter = NULL;
  1005. q->lock_ptr = &hb->lock;
  1006. wake_up_state(q->task, TASK_NORMAL);
  1007. }
  1008. /**
  1009. * futex_proxy_trylock_atomic() - Attempt an atomic lock for the top waiter
  1010. * @pifutex: the user address of the to futex
  1011. * @hb1: the from futex hash bucket, must be locked by the caller
  1012. * @hb2: the to futex hash bucket, must be locked by the caller
  1013. * @key1: the from futex key
  1014. * @key2: the to futex key
  1015. * @ps: address to store the pi_state pointer
  1016. * @set_waiters: force setting the FUTEX_WAITERS bit (1) or not (0)
  1017. *
  1018. * Try and get the lock on behalf of the top waiter if we can do it atomically.
  1019. * Wake the top waiter if we succeed. If the caller specified set_waiters,
  1020. * then direct futex_lock_pi_atomic() to force setting the FUTEX_WAITERS bit.
  1021. * hb1 and hb2 must be held by the caller.
  1022. *
  1023. * Returns:
  1024. * 0 - failed to acquire the lock atomicly
  1025. * 1 - acquired the lock
  1026. * <0 - error
  1027. */
  1028. static int futex_proxy_trylock_atomic(u32 __user *pifutex,
  1029. struct futex_hash_bucket *hb1,
  1030. struct futex_hash_bucket *hb2,
  1031. union futex_key *key1, union futex_key *key2,
  1032. struct futex_pi_state **ps, int set_waiters)
  1033. {
  1034. struct futex_q *top_waiter = NULL;
  1035. u32 curval;
  1036. int ret;
  1037. if (get_futex_value_locked(&curval, pifutex))
  1038. return -EFAULT;
  1039. /*
  1040. * Find the top_waiter and determine if there are additional waiters.
  1041. * If the caller intends to requeue more than 1 waiter to pifutex,
  1042. * force futex_lock_pi_atomic() to set the FUTEX_WAITERS bit now,
  1043. * as we have means to handle the possible fault. If not, don't set
  1044. * the bit unecessarily as it will force the subsequent unlock to enter
  1045. * the kernel.
  1046. */
  1047. top_waiter = futex_top_waiter(hb1, key1);
  1048. /* There are no waiters, nothing for us to do. */
  1049. if (!top_waiter)
  1050. return 0;
  1051. /* Ensure we requeue to the expected futex. */
  1052. if (!match_futex(top_waiter->requeue_pi_key, key2))
  1053. return -EINVAL;
  1054. /*
  1055. * Try to take the lock for top_waiter. Set the FUTEX_WAITERS bit in
  1056. * the contended case or if set_waiters is 1. The pi_state is returned
  1057. * in ps in contended cases.
  1058. */
  1059. ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
  1060. set_waiters);
  1061. if (ret == 1)
  1062. requeue_pi_wake_futex(top_waiter, key2, hb2);
  1063. return ret;
  1064. }
  1065. /**
  1066. * futex_requeue() - Requeue waiters from uaddr1 to uaddr2
  1067. * @uaddr1: source futex user address
  1068. * @flags: futex flags (FLAGS_SHARED, etc.)
  1069. * @uaddr2: target futex user address
  1070. * @nr_wake: number of waiters to wake (must be 1 for requeue_pi)
  1071. * @nr_requeue: number of waiters to requeue (0-INT_MAX)
  1072. * @cmpval: @uaddr1 expected value (or %NULL)
  1073. * @requeue_pi: if we are attempting to requeue from a non-pi futex to a
  1074. * pi futex (pi to pi requeue is not supported)
  1075. *
  1076. * Requeue waiters on uaddr1 to uaddr2. In the requeue_pi case, try to acquire
  1077. * uaddr2 atomically on behalf of the top waiter.
  1078. *
  1079. * Returns:
  1080. * >=0 - on success, the number of tasks requeued or woken
  1081. * <0 - on error
  1082. */
  1083. static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
  1084. u32 __user *uaddr2, int nr_wake, int nr_requeue,
  1085. u32 *cmpval, int requeue_pi)
  1086. {
  1087. union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
  1088. int drop_count = 0, task_count = 0, ret;
  1089. struct futex_pi_state *pi_state = NULL;
  1090. struct futex_hash_bucket *hb1, *hb2;
  1091. struct plist_head *head1;
  1092. struct futex_q *this, *next;
  1093. u32 curval2;
  1094. if (requeue_pi) {
  1095. /*
  1096. * requeue_pi requires a pi_state, try to allocate it now
  1097. * without any locks in case it fails.
  1098. */
  1099. if (refill_pi_state_cache())
  1100. return -ENOMEM;
  1101. /*
  1102. * requeue_pi must wake as many tasks as it can, up to nr_wake
  1103. * + nr_requeue, since it acquires the rt_mutex prior to
  1104. * returning to userspace, so as to not leave the rt_mutex with
  1105. * waiters and no owner. However, second and third wake-ups
  1106. * cannot be predicted as they involve race conditions with the
  1107. * first wake and a fault while looking up the pi_state. Both
  1108. * pthread_cond_signal() and pthread_cond_broadcast() should
  1109. * use nr_wake=1.
  1110. */
  1111. if (nr_wake != 1)
  1112. return -EINVAL;
  1113. }
  1114. retry:
  1115. if (pi_state != NULL) {
  1116. /*
  1117. * We will have to lookup the pi_state again, so free this one
  1118. * to keep the accounting correct.
  1119. */
  1120. free_pi_state(pi_state);
  1121. pi_state = NULL;
  1122. }
  1123. ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, VERIFY_READ);
  1124. if (unlikely(ret != 0))
  1125. goto out;
  1126. ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2,
  1127. requeue_pi ? VERIFY_WRITE : VERIFY_READ);
  1128. if (unlikely(ret != 0))
  1129. goto out_put_key1;
  1130. hb1 = hash_futex(&key1);
  1131. hb2 = hash_futex(&key2);
  1132. retry_private:
  1133. double_lock_hb(hb1, hb2);
  1134. if (likely(cmpval != NULL)) {
  1135. u32 curval;
  1136. ret = get_futex_value_locked(&curval, uaddr1);
  1137. if (unlikely(ret)) {
  1138. double_unlock_hb(hb1, hb2);
  1139. ret = get_user(curval, uaddr1);
  1140. if (ret)
  1141. goto out_put_keys;
  1142. if (!(flags & FLAGS_SHARED))
  1143. goto retry_private;
  1144. put_futex_key(&key2);
  1145. put_futex_key(&key1);
  1146. goto retry;
  1147. }
  1148. if (curval != *cmpval) {
  1149. ret = -EAGAIN;
  1150. goto out_unlock;
  1151. }
  1152. }
  1153. if (requeue_pi && (task_count - nr_wake < nr_requeue)) {
  1154. /*
  1155. * Attempt to acquire uaddr2 and wake the top waiter. If we
  1156. * intend to requeue waiters, force setting the FUTEX_WAITERS
  1157. * bit. We force this here where we are able to easily handle
  1158. * faults rather in the requeue loop below.
  1159. */
  1160. ret = futex_proxy_trylock_atomic(uaddr2, hb1, hb2, &key1,
  1161. &key2, &pi_state, nr_requeue);
  1162. /*
  1163. * At this point the top_waiter has either taken uaddr2 or is
  1164. * waiting on it. If the former, then the pi_state will not
  1165. * exist yet, look it up one more time to ensure we have a
  1166. * reference to it.
  1167. */
  1168. if (ret == 1) {
  1169. WARN_ON(pi_state);
  1170. drop_count++;
  1171. task_count++;
  1172. ret = get_futex_value_locked(&curval2, uaddr2);
  1173. if (!ret)
  1174. ret = lookup_pi_state(curval2, hb2, &key2,
  1175. &pi_state);
  1176. }
  1177. switch (ret) {
  1178. case 0:
  1179. break;
  1180. case -EFAULT:
  1181. double_unlock_hb(hb1, hb2);
  1182. put_futex_key(&key2);
  1183. put_futex_key(&key1);
  1184. ret = fault_in_user_writeable(uaddr2);
  1185. if (!ret)
  1186. goto retry;
  1187. goto out;
  1188. case -EAGAIN:
  1189. /* The owner was exiting, try again. */
  1190. double_unlock_hb(hb1, hb2);
  1191. put_futex_key(&key2);
  1192. put_futex_key(&key1);
  1193. cond_resched();
  1194. goto retry;
  1195. default:
  1196. goto out_unlock;
  1197. }
  1198. }
  1199. head1 = &hb1->chain;
  1200. plist_for_each_entry_safe(this, next, head1, list) {
  1201. if (task_count - nr_wake >= nr_requeue)
  1202. break;
  1203. if (!match_futex(&this->key, &key1))
  1204. continue;
  1205. /*
  1206. * FUTEX_WAIT_REQEUE_PI and FUTEX_CMP_REQUEUE_PI should always
  1207. * be paired with each other and no other futex ops.
  1208. */
  1209. if ((requeue_pi && !this->rt_waiter) ||
  1210. (!requeue_pi && this->rt_waiter)) {
  1211. ret = -EINVAL;
  1212. break;
  1213. }
  1214. /*
  1215. * Wake nr_wake waiters. For requeue_pi, if we acquired the
  1216. * lock, we already woke the top_waiter. If not, it will be
  1217. * woken by futex_unlock_pi().
  1218. */
  1219. if (++task_count <= nr_wake && !requeue_pi) {
  1220. wake_futex(this);
  1221. continue;
  1222. }
  1223. /* Ensure we requeue to the expected futex for requeue_pi. */
  1224. if (requeue_pi && !match_futex(this->requeue_pi_key, &key2)) {
  1225. ret = -EINVAL;
  1226. break;
  1227. }
  1228. /*
  1229. * Requeue nr_requeue waiters and possibly one more in the case
  1230. * of requeue_pi if we couldn't acquire the lock atomically.
  1231. */
  1232. if (requeue_pi) {
  1233. /* Prepare the waiter to take the rt_mutex. */
  1234. atomic_inc(&pi_state->refcount);
  1235. this->pi_state = pi_state;
  1236. ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,
  1237. this->rt_waiter,
  1238. this->task, 1);
  1239. if (ret == 1) {
  1240. /* We got the lock. */
  1241. requeue_pi_wake_futex(this, &key2, hb2);
  1242. drop_count++;
  1243. continue;
  1244. } else if (ret) {
  1245. /* -EDEADLK */
  1246. this->pi_state = NULL;
  1247. free_pi_state(pi_state);
  1248. goto out_unlock;
  1249. }
  1250. }
  1251. requeue_futex(this, hb1, hb2, &key2);
  1252. drop_count++;
  1253. }
  1254. out_unlock:
  1255. double_unlock_hb(hb1, hb2);
  1256. /*
  1257. * drop_futex_key_refs() must be called outside the spinlocks. During
  1258. * the requeue we moved futex_q's from the hash bucket at key1 to the
  1259. * one at key2 and updated their key pointer. We no longer need to
  1260. * hold the references to key1.
  1261. */
  1262. while (--drop_count >= 0)
  1263. drop_futex_key_refs(&key1);
  1264. out_put_keys:
  1265. put_futex_key(&key2);
  1266. out_put_key1:
  1267. put_futex_key(&key1);
  1268. out:
  1269. if (pi_state != NULL)
  1270. free_pi_state(pi_state);
  1271. return ret ? ret : task_count;
  1272. }
  1273. /* The key must be already stored in q->key. */
  1274. static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
  1275. __acquires(&hb->lock)
  1276. {
  1277. struct futex_hash_bucket *hb;
  1278. hb = hash_futex(&q->key);
  1279. q->lock_ptr = &hb->lock;
  1280. spin_lock(&hb->lock);
  1281. return hb;
  1282. }
  1283. static inline void
  1284. queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
  1285. __releases(&hb->lock)
  1286. {
  1287. spin_unlock(&hb->lock);
  1288. }
  1289. /**
  1290. * queue_me() - Enqueue the futex_q on the futex_hash_bucket
  1291. * @q: The futex_q to enqueue
  1292. * @hb: The destination hash bucket
  1293. *
  1294. * The hb->lock must be held by the caller, and is released here. A call to
  1295. * queue_me() is typically paired with exactly one call to unqueue_me(). The
  1296. * exceptions involve the PI related operations, which may use unqueue_me_pi()
  1297. * or nothing if the unqueue is done as part of the wake process and the unqueue
  1298. * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
  1299. * an example).
  1300. */
  1301. static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
  1302. __releases(&hb->lock)
  1303. {
  1304. int prio;
  1305. /*
  1306. * The priority used to register this element is
  1307. * - either the real thread-priority for the real-time threads
  1308. * (i.e. threads with a priority lower than MAX_RT_PRIO)
  1309. * - or MAX_RT_PRIO for non-RT threads.
  1310. * Thus, all RT-threads are woken first in priority order, and
  1311. * the others are woken last, in FIFO order.
  1312. */
  1313. prio = min(current->normal_prio, MAX_RT_PRIO);
  1314. plist_node_init(&q->list, prio);
  1315. plist_add(&q->list, &hb->chain);
  1316. q->task = current;
  1317. spin_unlock(&hb->lock);
  1318. }
  1319. /**
  1320. * unqueue_me() - Remove the futex_q from its futex_hash_bucket
  1321. * @q: The futex_q to unqueue
  1322. *
  1323. * The q->lock_ptr must not be held by the caller. A call to unqueue_me() must
  1324. * be paired with exactly one earlier call to queue_me().
  1325. *
  1326. * Returns:
  1327. * 1 - if the futex_q was still queued (and we removed unqueued it)
  1328. * 0 - if the futex_q was already removed by the waking thread
  1329. */
  1330. static int unqueue_me(struct futex_q *q)
  1331. {
  1332. spinlock_t *lock_ptr;
  1333. int ret = 0;
  1334. /* In the common case we don't take the spinlock, which is nice. */
  1335. retry:
  1336. lock_ptr = q->lock_ptr;
  1337. barrier();
  1338. if (lock_ptr != NULL) {
  1339. spin_lock(lock_ptr);
  1340. /*
  1341. * q->lock_ptr can change between reading it and
  1342. * spin_lock(), causing us to take the wrong lock. This
  1343. * corrects the race condition.
  1344. *
  1345. * Reasoning goes like this: if we have the wrong lock,
  1346. * q->lock_ptr must have changed (maybe several times)
  1347. * between reading it and the spin_lock(). It can
  1348. * change again after the spin_lock() but only if it was
  1349. * already changed before the spin_lock(). It cannot,
  1350. * however, change back to the original value. Therefore
  1351. * we can detect whether we acquired the correct lock.
  1352. */
  1353. if (unlikely(lock_ptr != q->lock_ptr)) {
  1354. spin_unlock(lock_ptr);
  1355. goto retry;
  1356. }
  1357. __unqueue_futex(q);
  1358. BUG_ON(q->pi_state);
  1359. spin_unlock(lock_ptr);
  1360. ret = 1;
  1361. }
  1362. drop_futex_key_refs(&q->key);
  1363. return ret;
  1364. }
  1365. /*
  1366. * PI futexes can not be requeued and must remove themself from the
  1367. * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
  1368. * and dropped here.
  1369. */
  1370. static void unqueue_me_pi(struct futex_q *q)
  1371. __releases(q->lock_ptr)
  1372. {
  1373. __unqueue_futex(q);
  1374. BUG_ON(!q->pi_state);
  1375. free_pi_state(q->pi_state);
  1376. q->pi_state = NULL;
  1377. spin_unlock(q->lock_ptr);
  1378. }
  1379. /*
  1380. * Fixup the pi_state owner with the new owner.
  1381. *
  1382. * Must be called with hash bucket lock held and mm->sem held for non
  1383. * private futexes.
  1384. */
  1385. static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
  1386. struct task_struct *newowner)
  1387. {
  1388. u32 newtid = task_pid_vnr(newowner) | FUTEX_WAITERS;
  1389. struct futex_pi_state *pi_state = q->pi_state;
  1390. struct task_struct *oldowner = pi_state->owner;
  1391. u32 uval, uninitialized_var(curval), newval;
  1392. int ret;
  1393. /* Owner died? */
  1394. if (!pi_state->owner)
  1395. newtid |= FUTEX_OWNER_DIED;
  1396. /*
  1397. * We are here either because we stole the rtmutex from the
  1398. * previous highest priority waiter or we are the highest priority
  1399. * waiter but failed to get the rtmutex the first time.
  1400. * We have to replace the newowner TID in the user space variable.
  1401. * This must be atomic as we have to preserve the owner died bit here.
  1402. *
  1403. * Note: We write the user space value _before_ changing the pi_state
  1404. * because we can fault here. Imagine swapped out pages or a fork
  1405. * that marked all the anonymous memory readonly for cow.
  1406. *
  1407. * Modifying pi_state _before_ the user space value would
  1408. * leave the pi_state in an inconsistent state when we fault
  1409. * here, because we need to drop the hash bucket lock to
  1410. * handle the fault. This might be observed in the PID check
  1411. * in lookup_pi_state.
  1412. */
  1413. retry:
  1414. if (get_futex_value_locked(&uval, uaddr))
  1415. goto handle_fault;
  1416. while (1) {
  1417. newval = (uval & FUTEX_OWNER_DIED) | newtid;
  1418. if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval))
  1419. goto handle_fault;
  1420. if (curval == uval)
  1421. break;
  1422. uval = curval;
  1423. }
  1424. /*
  1425. * We fixed up user space. Now we need to fix the pi_state
  1426. * itself.
  1427. */
  1428. if (pi_state->owner != NULL) {
  1429. raw_spin_lock_irq(&pi_state->owner->pi_lock);
  1430. WARN_ON(list_empty(&pi_state->list));
  1431. list_del_init(&pi_state->list);
  1432. raw_spin_unlock_irq(&pi_state->owner->pi_lock);
  1433. }
  1434. pi_state->owner = newowner;
  1435. raw_spin_lock_irq(&newowner->pi_lock);
  1436. WARN_ON(!list_empty(&pi_state->list));
  1437. list_add(&pi_state->list, &newowner->pi_state_list);
  1438. raw_spin_unlock_irq(&newowner->pi_lock);
  1439. return 0;
  1440. /*
  1441. * To handle the page fault we need to drop the hash bucket
  1442. * lock here. That gives the other task (either the highest priority
  1443. * waiter itself or the task which stole the rtmutex) the
  1444. * chance to try the fixup of the pi_state. So once we are
  1445. * back from handling the fault we need to check the pi_state
  1446. * after reacquiring the hash bucket lock and before trying to
  1447. * do another fixup. When the fixup has been done already we
  1448. * simply return.
  1449. */
  1450. handle_fault:
  1451. spin_unlock(q->lock_ptr);
  1452. ret = fault_in_user_writeable(uaddr);
  1453. spin_lock(q->lock_ptr);
  1454. /*
  1455. * Check if someone else fixed it for us:
  1456. */
  1457. if (pi_state->owner != oldowner)
  1458. return 0;
  1459. if (ret)
  1460. return ret;
  1461. goto retry;
  1462. }
  1463. static long futex_wait_restart(struct restart_block *restart);
  1464. /**
  1465. * fixup_owner() - Post lock pi_state and corner case management
  1466. * @uaddr: user address of the futex
  1467. * @q: futex_q (contains pi_state and access to the rt_mutex)
  1468. * @locked: if the attempt to take the rt_mutex succeeded (1) or not (0)
  1469. *
  1470. * After attempting to lock an rt_mutex, this function is called to cleanup
  1471. * the pi_state owner as well as handle race conditions that may allow us to
  1472. * acquire the lock. Must be called with the hb lock held.
  1473. *
  1474. * Returns:
  1475. * 1 - success, lock taken
  1476. * 0 - success, lock not taken
  1477. * <0 - on error (-EFAULT)
  1478. */
  1479. static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
  1480. {
  1481. struct task_struct *owner;
  1482. int ret = 0;
  1483. if (locked) {
  1484. /*
  1485. * Got the lock. We might not be the anticipated owner if we
  1486. * did a lock-steal - fix up the PI-state in that case:
  1487. */
  1488. if (q->pi_state->owner != current)
  1489. ret = fixup_pi_state_owner(uaddr, q, current);
  1490. goto out;
  1491. }
  1492. /*
  1493. * Catch the rare case, where the lock was released when we were on the
  1494. * way back before we locked the hash bucket.
  1495. */
  1496. if (q->pi_state->owner == current) {
  1497. /*
  1498. * Try to get the rt_mutex now. This might fail as some other
  1499. * task acquired the rt_mutex after we removed ourself from the
  1500. * rt_mutex waiters list.
  1501. */
  1502. if (rt_mutex_trylock(&q->pi_state->pi_mutex)) {
  1503. locked = 1;
  1504. goto out;
  1505. }
  1506. /*
  1507. * pi_state is incorrect, some other task did a lock steal and
  1508. * we returned due to timeout or signal without taking the
  1509. * rt_mutex. Too late.
  1510. */
  1511. raw_spin_lock(&q->pi_state->pi_mutex.wait_lock);
  1512. owner = rt_mutex_owner(&q->pi_state->pi_mutex);
  1513. if (!owner)
  1514. owner = rt_mutex_next_owner(&q->pi_state->pi_mutex);
  1515. raw_spin_unlock(&q->pi_state->pi_mutex.wait_lock);
  1516. ret = fixup_pi_state_owner(uaddr, q, owner);
  1517. goto out;
  1518. }
  1519. /*
  1520. * Paranoia check. If we did not take the lock, then we should not be
  1521. * the owner of the rt_mutex.
  1522. */
  1523. if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
  1524. printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "
  1525. "pi-state %p\n", ret,
  1526. q->pi_state->pi_mutex.owner,
  1527. q->pi_state->owner);
  1528. out:
  1529. return ret ? ret : locked;
  1530. }
  1531. /**
  1532. * futex_wait_queue_me() - queue_me() and wait for wakeup, timeout, or signal
  1533. * @hb: the futex hash bucket, must be locked by the caller
  1534. * @q: the futex_q to queue up on
  1535. * @timeout: the prepared hrtimer_sleeper, or null for no timeout
  1536. */
  1537. static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
  1538. struct hrtimer_sleeper *timeout)
  1539. {
  1540. /*
  1541. * The task state is guaranteed to be set before another task can
  1542. * wake it. set_current_state() is implemented using set_mb() and
  1543. * queue_me() calls spin_unlock() upon completion, both serializing
  1544. * access to the hash list and forcing another memory barrier.
  1545. */
  1546. set_current_state(TASK_INTERRUPTIBLE);
  1547. queue_me(q, hb);
  1548. /* Arm the timer */
  1549. if (timeout) {
  1550. hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
  1551. if (!hrtimer_active(&timeout->timer))
  1552. timeout->task = NULL;
  1553. }
  1554. /*
  1555. * If we have been removed from the hash list, then another task
  1556. * has tried to wake us, and we can skip the call to schedule().
  1557. */
  1558. if (likely(!plist_node_empty(&q->list))) {
  1559. /*
  1560. * If the timer has already expired, current will already be
  1561. * flagged for rescheduling. Only call schedule if there
  1562. * is no timeout, or if it has yet to expire.
  1563. */
  1564. if (!timeout || timeout->task)
  1565. schedule();
  1566. }
  1567. __set_current_state(TASK_RUNNING);
  1568. }
  1569. /**
  1570. * futex_wait_setup() - Prepare to wait on a futex
  1571. * @uaddr: the futex userspace address
  1572. * @val: the expected value
  1573. * @flags: futex flags (FLAGS_SHARED, etc.)
  1574. * @q: the associated futex_q
  1575. * @hb: storage for hash_bucket pointer to be returned to caller
  1576. *
  1577. * Setup the futex_q and locate the hash_bucket. Get the futex value and
  1578. * compare it with the expected value. Handle atomic faults internally.
  1579. * Return with the hb lock held and a q.key reference on success, and unlocked
  1580. * with no q.key reference on failure.
  1581. *
  1582. * Returns:
  1583. * 0 - uaddr contains val and hb has been locked
  1584. * <1 - -EFAULT or -EWOULDBLOCK (uaddr does not contain val) and hb is unlocked
  1585. */
  1586. static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
  1587. struct futex_q *q, struct futex_hash_bucket **hb)
  1588. {
  1589. u32 uval;
  1590. int ret;
  1591. /*
  1592. * Access the page AFTER the hash-bucket is locked.
  1593. * Order is important:
  1594. *
  1595. * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
  1596. * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); }
  1597. *
  1598. * The basic logical guarantee of a futex is that it blocks ONLY
  1599. * if cond(var) is known to be true at the time of blocking, for
  1600. * any cond. If we locked the hash-bucket after testing *uaddr, that
  1601. * would open a race condition where we could block indefinitely with
  1602. * cond(var) false, which would violate the guarantee.
  1603. *
  1604. * On the other hand, we insert q and release the hash-bucket only
  1605. * after testing *uaddr. This guarantees that futex_wait() will NOT
  1606. * absorb a wakeup if *uaddr does not match the desired values
  1607. * while the syscall executes.
  1608. */
  1609. retry:
  1610. ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key, VERIFY_READ);
  1611. if (unlikely(ret != 0))
  1612. return ret;
  1613. retry_private:
  1614. *hb = queue_lock(q);
  1615. ret = get_futex_value_locked(&uval, uaddr);
  1616. if (ret) {
  1617. queue_unlock(q, *hb);
  1618. ret = get_user(uval, uaddr);
  1619. if (ret)
  1620. goto out;
  1621. if (!(flags & FLAGS_SHARED))
  1622. goto retry_private;
  1623. put_futex_key(&q->key);
  1624. goto retry;
  1625. }
  1626. if (uval != val) {
  1627. queue_unlock(q, *hb);
  1628. ret = -EWOULDBLOCK;
  1629. }
  1630. out:
  1631. if (ret)
  1632. put_futex_key(&q->key);
  1633. return ret;
  1634. }
  1635. static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
  1636. ktime_t *abs_time, u32 bitset)
  1637. {
  1638. struct hrtimer_sleeper timeout, *to = NULL;
  1639. struct restart_block *restart;
  1640. struct futex_hash_bucket *hb;
  1641. struct futex_q q = futex_q_init;
  1642. int ret;
  1643. if (!bitset)
  1644. return -EINVAL;
  1645. q.bitset = bitset;
  1646. if (abs_time) {
  1647. to = &timeout;
  1648. hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
  1649. CLOCK_REALTIME : CLOCK_MONOTONIC,
  1650. HRTIMER_MODE_ABS);
  1651. hrtimer_init_sleeper(to, current);
  1652. hrtimer_set_expires_range_ns(&to->timer, *abs_time,
  1653. current->timer_slack_ns);
  1654. }
  1655. retry:
  1656. /*
  1657. * Prepare to wait on uaddr. On success, holds hb lock and increments
  1658. * q.key refs.
  1659. */
  1660. ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
  1661. if (ret)
  1662. goto out;
  1663. /* queue_me and wait for wakeup, timeout, or a signal. */
  1664. futex_wait_queue_me(hb, &q, to);
  1665. /* If we were woken (and unqueued), we succeeded, whatever. */
  1666. ret = 0;
  1667. /* unqueue_me() drops q.key ref */
  1668. if (!unqueue_me(&q))
  1669. goto out;
  1670. ret = -ETIMEDOUT;
  1671. if (to && !to->task)
  1672. goto out;
  1673. /*
  1674. * We expect signal_pending(current), but we might be the
  1675. * victim of a spurious wakeup as well.
  1676. */
  1677. if (!signal_pending(current))
  1678. goto retry;
  1679. ret = -ERESTARTSYS;
  1680. if (!abs_time)
  1681. goto out;
  1682. restart = &current_thread_info()->restart_block;
  1683. restart->fn = futex_wait_restart;
  1684. restart->futex.uaddr = uaddr;
  1685. restart->futex.val = val;
  1686. restart->futex.time = abs_time->tv64;
  1687. restart->futex.bitset = bitset;
  1688. restart->futex.flags = flags | FLAGS_HAS_TIMEOUT;
  1689. ret = -ERESTART_RESTARTBLOCK;
  1690. out:
  1691. if (to) {
  1692. hrtimer_cancel(&to->timer);
  1693. destroy_hrtimer_on_stack(&to->timer);
  1694. }
  1695. return ret;
  1696. }
  1697. static long futex_wait_restart(struct restart_block *restart)
  1698. {
  1699. u32 __user *uaddr = restart->futex.uaddr;
  1700. ktime_t t, *tp = NULL;
  1701. if (restart->futex.flags & FLAGS_HAS_TIMEOUT) {
  1702. t.tv64 = restart->futex.time;
  1703. tp = &t;
  1704. }
  1705. restart->fn = do_no_restart_syscall;
  1706. return (long)futex_wait(uaddr, restart->futex.flags,
  1707. restart->futex.val, tp, restart->futex.bitset);
  1708. }
  1709. /*
  1710. * Userspace tried a 0 -> TID atomic transition of the futex value
  1711. * and failed. The kernel side here does the whole locking operation:
  1712. * if there are waiters then it will block, it does PI, etc. (Due to
  1713. * races the kernel might see a 0 value of the futex too.)
  1714. */
  1715. static int futex_lock_pi(u32 __user *uaddr, unsigned int flags, int detect,
  1716. ktime_t *time, int trylock)
  1717. {
  1718. struct hrtimer_sleeper timeout, *to = NULL;
  1719. struct futex_hash_bucket *hb;
  1720. struct futex_q q = futex_q_init;
  1721. int res, ret;
  1722. if (refill_pi_state_cache())
  1723. return -ENOMEM;
  1724. if (time) {
  1725. to = &timeout;
  1726. hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
  1727. HRTIMER_MODE_ABS);
  1728. hrtimer_init_sleeper(to, current);
  1729. hrtimer_set_expires(&to->timer, *time);
  1730. }
  1731. retry:
  1732. ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, VERIFY_WRITE);
  1733. if (unlikely(ret != 0))
  1734. goto out;
  1735. retry_private:
  1736. hb = queue_lock(&q);
  1737. ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &q.pi_state, current, 0);
  1738. if (unlikely(ret)) {
  1739. switch (ret) {
  1740. case 1:
  1741. /* We got the lock. */
  1742. ret = 0;
  1743. goto out_unlock_put_key;
  1744. case -EFAULT:
  1745. goto uaddr_faulted;
  1746. case -EAGAIN:
  1747. /*
  1748. * Task is exiting and we just wait for the
  1749. * exit to complete.
  1750. */
  1751. queue_unlock(&q, hb);
  1752. put_futex_key(&q.key);
  1753. cond_resched();
  1754. goto retry;
  1755. default:
  1756. goto out_unlock_put_key;
  1757. }
  1758. }
  1759. /*
  1760. * Only actually queue now that the atomic ops are done:
  1761. */
  1762. queue_me(&q, hb);
  1763. WARN_ON(!q.pi_state);
  1764. /*
  1765. * Block on the PI mutex:
  1766. */
  1767. if (!trylock)
  1768. ret = rt_mutex_timed_lock(&q.pi_state->pi_mutex, to, 1);
  1769. else {
  1770. ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
  1771. /* Fixup the trylock return value: */
  1772. ret = ret ? 0 : -EWOULDBLOCK;
  1773. }
  1774. spin_lock(q.lock_ptr);
  1775. /*
  1776. * Fixup the pi_state owner and possibly acquire the lock if we
  1777. * haven't already.
  1778. */
  1779. res = fixup_owner(uaddr, &q, !ret);
  1780. /*
  1781. * If fixup_owner() returned an error, proprogate that. If it acquired
  1782. * the lock, clear our -ETIMEDOUT or -EINTR.
  1783. */
  1784. if (res)
  1785. ret = (res < 0) ? res : 0;
  1786. /*
  1787. * If fixup_owner() faulted and was unable to handle the fault, unlock
  1788. * it and return the fault to userspace.
  1789. */
  1790. if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current))
  1791. rt_mutex_unlock(&q.pi_state->pi_mutex);
  1792. /* Unqueue and drop the lock */
  1793. unqueue_me_pi(&q);
  1794. goto out_put_key;
  1795. out_unlock_put_key:
  1796. queue_unlock(&q, hb);
  1797. out_put_key:
  1798. put_futex_key(&q.key);
  1799. out:
  1800. if (to)
  1801. destroy_hrtimer_on_stack(&to->timer);
  1802. return ret != -EINTR ? ret : -ERESTARTNOINTR;
  1803. uaddr_faulted:
  1804. queue_unlock(&q, hb);
  1805. ret = fault_in_user_writeable(uaddr);
  1806. if (ret)
  1807. goto out_put_key;
  1808. if (!(flags & FLAGS_SHARED))
  1809. goto retry_private;
  1810. put_futex_key(&q.key);
  1811. goto retry;
  1812. }
  1813. /*
  1814. * Userspace attempted a TID -> 0 atomic transition, and failed.
  1815. * This is the in-kernel slowpath: we look up the PI state (if any),
  1816. * and do the rt-mutex unlock.
  1817. */
  1818. static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
  1819. {
  1820. struct futex_hash_bucket *hb;
  1821. struct futex_q *this, *next;
  1822. struct plist_head *head;
  1823. union futex_key key = FUTEX_KEY_INIT;
  1824. u32 uval, vpid = task_pid_vnr(current);
  1825. int ret;
  1826. retry:
  1827. if (get_user(uval, uaddr))
  1828. return -EFAULT;
  1829. /*
  1830. * We release only a lock we actually own:
  1831. */
  1832. if ((uval & FUTEX_TID_MASK) != vpid)
  1833. return -EPERM;
  1834. ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, VERIFY_WRITE);
  1835. if (unlikely(ret != 0))
  1836. goto out;
  1837. hb = hash_futex(&key);
  1838. spin_lock(&hb->lock);
  1839. /*
  1840. * To avoid races, try to do the TID -> 0 atomic transition
  1841. * again. If it succeeds then we can return without waking
  1842. * anyone else up:
  1843. */
  1844. if (!(uval & FUTEX_OWNER_DIED) &&
  1845. cmpxchg_futex_value_locked(&uval, uaddr, vpid, 0))
  1846. goto pi_faulted;
  1847. /*
  1848. * Rare case: we managed to release the lock atomically,
  1849. * no need to wake anyone else up:
  1850. */
  1851. if (unlikely(uval == vpid))
  1852. goto out_unlock;
  1853. /*
  1854. * Ok, other tasks may need to be woken up - check waiters
  1855. * and do the wakeup if necessary:
  1856. */
  1857. head = &hb->chain;
  1858. plist_for_each_entry_safe(this, next, head, list) {
  1859. if (!match_futex (&this->key, &key))
  1860. continue;
  1861. ret = wake_futex_pi(uaddr, uval, this);
  1862. /*
  1863. * The atomic access to the futex value
  1864. * generated a pagefault, so retry the
  1865. * user-access and the wakeup:
  1866. */
  1867. if (ret == -EFAULT)
  1868. goto pi_faulted;
  1869. goto out_unlock;
  1870. }
  1871. /*
  1872. * No waiters - kernel unlocks the futex:
  1873. */
  1874. if (!(uval & FUTEX_OWNER_DIED)) {
  1875. ret = unlock_futex_pi(uaddr, uval);
  1876. if (ret == -EFAULT)
  1877. goto pi_faulted;
  1878. }
  1879. out_unlock:
  1880. spin_unlock(&hb->lock);
  1881. put_futex_key(&key);
  1882. out:
  1883. return ret;
  1884. pi_faulted:
  1885. spin_unlock(&hb->lock);
  1886. put_futex_key(&key);
  1887. ret = fault_in_user_writeable(uaddr);
  1888. if (!ret)
  1889. goto retry;
  1890. return ret;
  1891. }
  1892. /**
  1893. * handle_early_requeue_pi_wakeup() - Detect early wakeup on the initial futex
  1894. * @hb: the hash_bucket futex_q was original enqueued on
  1895. * @q: the futex_q woken while waiting to be requeued
  1896. * @key2: the futex_key of the requeue target futex
  1897. * @timeout: the timeout associated with the wait (NULL if none)
  1898. *
  1899. * Detect if the task was woken on the initial futex as opposed to the requeue
  1900. * target futex. If so, determine if it was a timeout or a signal that caused
  1901. * the wakeup and return the appropriate error code to the caller. Must be
  1902. * called with the hb lock held.
  1903. *
  1904. * Returns
  1905. * 0 - no early wakeup detected
  1906. * <0 - -ETIMEDOUT or -ERESTARTNOINTR
  1907. */
  1908. static inline
  1909. int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb,
  1910. struct futex_q *q, union futex_key *key2,
  1911. struct hrtimer_sleeper *timeout)
  1912. {
  1913. int ret = 0;
  1914. /*
  1915. * With the hb lock held, we avoid races while we process the wakeup.
  1916. * We only need to hold hb (and not hb2) to ensure atomicity as the
  1917. * wakeup code can't change q.key from uaddr to uaddr2 if we hold hb.
  1918. * It can't be requeued from uaddr2 to something else since we don't
  1919. * support a PI aware source futex for requeue.
  1920. */
  1921. if (!match_futex(&q->key, key2)) {
  1922. WARN_ON(q->lock_ptr && (&hb->lock != q->lock_ptr));
  1923. /*
  1924. * We were woken prior to requeue by a timeout or a signal.
  1925. * Unqueue the futex_q and determine which it was.
  1926. */
  1927. plist_del(&q->list, &hb->chain);
  1928. /* Handle spurious wakeups gracefully */
  1929. ret = -EWOULDBLOCK;
  1930. if (timeout && !timeout->task)
  1931. ret = -ETIMEDOUT;
  1932. else if (signal_pending(current))
  1933. ret = -ERESTARTNOINTR;
  1934. }
  1935. return ret;
  1936. }
  1937. /**
  1938. * futex_wait_requeue_pi() - Wait on uaddr and take uaddr2
  1939. * @uaddr: the futex we initially wait on (non-pi)
  1940. * @flags: futex flags (FLAGS_SHARED, FLAGS_CLOCKRT, etc.), they must be
  1941. * the same type, no requeueing from private to shared, etc.
  1942. * @val: the expected value of uaddr
  1943. * @abs_time: absolute timeout
  1944. * @bitset: 32 bit wakeup bitset set by userspace, defaults to all
  1945. * @clockrt: whether to use CLOCK_REALTIME (1) or CLOCK_MONOTONIC (0)
  1946. * @uaddr2: the pi futex we will take prior to returning to user-space
  1947. *
  1948. * The caller will wait on uaddr and will be requeued by futex_requeue() to
  1949. * uaddr2 which must be PI aware and unique from uaddr. Normal wakeup will wake
  1950. * on uaddr2 and complete the acquisition of the rt_mutex prior to returning to
  1951. * userspace. This ensures the rt_mutex maintains an owner when it has waiters;
  1952. * without one, the pi logic would not know which task to boost/deboost, if
  1953. * there was a need to.
  1954. *
  1955. * We call schedule in futex_wait_queue_me() when we enqueue and return there
  1956. * via the following:
  1957. * 1) wakeup on uaddr2 after an atomic lock acquisition by futex_requeue()
  1958. * 2) wakeup on uaddr2 after a requeue
  1959. * 3) signal
  1960. * 4) timeout
  1961. *
  1962. * If 3, cleanup and return -ERESTARTNOINTR.
  1963. *
  1964. * If 2, we may then block on trying to take the rt_mutex and return via:
  1965. * 5) successful lock
  1966. * 6) signal
  1967. * 7) timeout
  1968. * 8) other lock acquisition failure
  1969. *
  1970. * If 6, return -EWOULDBLOCK (restarting the syscall would do the same).
  1971. *
  1972. * If 4 or 7, we cleanup and return with -ETIMEDOUT.
  1973. *
  1974. * Returns:
  1975. * 0 - On success
  1976. * <0 - On error
  1977. */
  1978. static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
  1979. u32 val, ktime_t *abs_time, u32 bitset,
  1980. u32 __user *uaddr2)
  1981. {
  1982. struct hrtimer_sleeper timeout, *to = NULL;
  1983. struct rt_mutex_waiter rt_waiter;
  1984. struct rt_mutex *pi_mutex = NULL;
  1985. struct futex_hash_bucket *hb;
  1986. union futex_key key2 = FUTEX_KEY_INIT;
  1987. struct futex_q q = futex_q_init;
  1988. int res, ret;
  1989. if (uaddr == uaddr2)
  1990. return -EINVAL;
  1991. if (!bitset)
  1992. return -EINVAL;
  1993. if (abs_time) {
  1994. to = &timeout;
  1995. hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
  1996. CLOCK_REALTIME : CLOCK_MONOTONIC,
  1997. HRTIMER_MODE_ABS);
  1998. hrtimer_init_sleeper(to, current);
  1999. hrtimer_set_expires_range_ns(&to->timer, *abs_time,
  2000. current->timer_slack_ns);
  2001. }
  2002. /*
  2003. * The waiter is allocated on our stack, manipulated by the requeue
  2004. * code while we sleep on uaddr.
  2005. */
  2006. debug_rt_mutex_init_waiter(&rt_waiter);
  2007. rt_waiter.task = NULL;
  2008. ret = get_futex_key(uaddr2, flags & FLAGS_SHARED, &key2, VERIFY_WRITE);
  2009. if (unlikely(ret != 0))
  2010. goto out;
  2011. q.bitset = bitset;
  2012. q.rt_waiter = &rt_waiter;
  2013. q.requeue_pi_key = &key2;
  2014. /*
  2015. * Prepare to wait on uaddr. On success, increments q.key (key1) ref
  2016. * count.
  2017. */
  2018. ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
  2019. if (ret)
  2020. goto out_key2;
  2021. /* Queue the futex_q, drop the hb lock, wait for wakeup. */
  2022. futex_wait_queue_me(hb, &q, to);
  2023. spin_lock(&hb->lock);
  2024. ret = handle_early_requeue_pi_wakeup(hb, &q, &key2, to);
  2025. spin_unlock(&hb->lock);
  2026. if (ret)
  2027. goto out_put_keys;
  2028. /*
  2029. * In order for us to be here, we know our q.key == key2, and since
  2030. * we took the hb->lock above, we also know that futex_requeue() has
  2031. * completed and we no longer have to concern ourselves with a wakeup
  2032. * race with the atomic proxy lock acquisition by the requeue code. The
  2033. * futex_requeue dropped our key1 reference and incremented our key2
  2034. * reference count.
  2035. */
  2036. /* Check if the requeue code acquired the second futex for us. */
  2037. if (!q.rt_waiter) {
  2038. /*
  2039. * Got the lock. We might not be the anticipated owner if we
  2040. * did a lock-steal - fix up the PI-state in that case.
  2041. */
  2042. if (q.pi_state && (q.pi_state->owner != current)) {
  2043. spin_lock(q.lock_ptr);
  2044. ret = fixup_pi_state_owner(uaddr2, &q, current);
  2045. spin_unlock(q.lock_ptr);
  2046. }
  2047. } else {
  2048. /*
  2049. * We have been woken up by futex_unlock_pi(), a timeout, or a
  2050. * signal. futex_unlock_pi() will not destroy the lock_ptr nor
  2051. * the pi_state.
  2052. */
  2053. WARN_ON(!q.pi_state);
  2054. pi_mutex = &q.pi_state->pi_mutex;
  2055. ret = rt_mutex_finish_proxy_lock(pi_mutex, to, &rt_waiter, 1);
  2056. debug_rt_mutex_free_waiter(&rt_waiter);
  2057. spin_lock(q.lock_ptr);
  2058. /*
  2059. * Fixup the pi_state owner and possibly acquire the lock if we
  2060. * haven't already.
  2061. */
  2062. res = fixup_owner(uaddr2, &q, !ret);
  2063. /*
  2064. * If fixup_owner() returned an error, proprogate that. If it
  2065. * acquired the lock, clear -ETIMEDOUT or -EINTR.
  2066. */
  2067. if (res)
  2068. ret = (res < 0) ? res : 0;
  2069. /* Unqueue and drop the lock. */
  2070. unqueue_me_pi(&q);
  2071. }
  2072. /*
  2073. * If fixup_pi_state_owner() faulted and was unable to handle the
  2074. * fault, unlock the rt_mutex and return the fault to userspace.
  2075. */
  2076. if (ret == -EFAULT) {
  2077. if (pi_mutex && rt_mutex_owner(pi_mutex) == current)
  2078. rt_mutex_unlock(pi_mutex);
  2079. } else if (ret == -EINTR) {
  2080. /*
  2081. * We've already been requeued, but cannot restart by calling
  2082. * futex_lock_pi() directly. We could restart this syscall, but
  2083. * it would detect that the user space "val" changed and return
  2084. * -EWOULDBLOCK. Save the overhead of the restart and return
  2085. * -EWOULDBLOCK directly.
  2086. */
  2087. ret = -EWOULDBLOCK;
  2088. }
  2089. out_put_keys:
  2090. put_futex_key(&q.key);
  2091. out_key2:
  2092. put_futex_key(&key2);
  2093. out:
  2094. if (to) {
  2095. hrtimer_cancel(&to->timer);
  2096. destroy_hrtimer_on_stack(&to->timer);
  2097. }
  2098. return ret;
  2099. }
  2100. /*
  2101. * Support for robust futexes: the kernel cleans up held futexes at
  2102. * thread exit time.
  2103. *
  2104. * Implementation: user-space maintains a per-thread list of locks it
  2105. * is holding. Upon do_exit(), the kernel carefully walks this list,
  2106. * and marks all locks that are owned by this thread with the
  2107. * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
  2108. * always manipulated with the lock held, so the list is private and
  2109. * per-thread. Userspace also maintains a per-thread 'list_op_pending'
  2110. * field, to allow the kernel to clean up if the thread dies after
  2111. * acquiring the lock, but just before it could have added itself to
  2112. * the list. There can only be one such pending lock.
  2113. */
  2114. /**
  2115. * sys_set_robust_list() - Set the robust-futex list head of a task
  2116. * @head: pointer to the list-head
  2117. * @len: length of the list-head, as userspace expects
  2118. */
  2119. SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head,
  2120. size_t, len)
  2121. {
  2122. if (!futex_cmpxchg_enabled)
  2123. return -ENOSYS;
  2124. /*
  2125. * The kernel knows only one size for now:
  2126. */
  2127. if (unlikely(len != sizeof(*head)))
  2128. return -EINVAL;
  2129. current->robust_list = head;
  2130. return 0;
  2131. }
  2132. /**
  2133. * sys_get_robust_list() - Get the robust-futex list head of a task
  2134. * @pid: pid of the process [zero for current task]
  2135. * @head_ptr: pointer to a list-head pointer, the kernel fills it in
  2136. * @len_ptr: pointer to a length field, the kernel fills in the header size
  2137. */
  2138. SYSCALL_DEFINE3(get_robust_list, int, pid,
  2139. struct robust_list_head __user * __user *, head_ptr,
  2140. size_t __user *, len_ptr)
  2141. {
  2142. struct robust_list_head __user *head;
  2143. unsigned long ret;
  2144. struct task_struct *p;
  2145. if (!futex_cmpxchg_enabled)
  2146. return -ENOSYS;
  2147. WARN_ONCE(1, "deprecated: get_robust_list will be deleted in 2013.\n");
  2148. rcu_read_lock();
  2149. ret = -ESRCH;
  2150. if (!pid)
  2151. p = current;
  2152. else {
  2153. p = find_task_by_vpid(pid);
  2154. if (!p)
  2155. goto err_unlock;
  2156. }
  2157. ret = -EPERM;
  2158. if (!ptrace_may_access(p, PTRACE_MODE_READ))
  2159. goto err_unlock;
  2160. head = p->robust_list;
  2161. rcu_read_unlock();
  2162. if (put_user(sizeof(*head), len_ptr))
  2163. return -EFAULT;
  2164. return put_user(head, head_ptr);
  2165. err_unlock:
  2166. rcu_read_unlock();
  2167. return ret;
  2168. }
  2169. /*
  2170. * Process a futex-list entry, check whether it's owned by the
  2171. * dying task, and do notification if so:
  2172. */
  2173. int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
  2174. {
  2175. u32 uval, uninitialized_var(nval), mval;
  2176. retry:
  2177. if (get_user(uval, uaddr))
  2178. return -1;
  2179. if ((uval & FUTEX_TID_MASK) == task_pid_vnr(curr)) {
  2180. /*
  2181. * Ok, this dying thread is truly holding a futex
  2182. * of interest. Set the OWNER_DIED bit atomically
  2183. * via cmpxchg, and if the value had FUTEX_WAITERS
  2184. * set, wake up a waiter (if any). (We have to do a
  2185. * futex_wake() even if OWNER_DIED is already set -
  2186. * to handle the rare but possible case of recursive
  2187. * thread-death.) The rest of the cleanup is done in
  2188. * userspace.
  2189. */
  2190. mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
  2191. /*
  2192. * We are not holding a lock here, but we want to have
  2193. * the pagefault_disable/enable() protection because
  2194. * we want to handle the fault gracefully. If the
  2195. * access fails we try to fault in the futex with R/W
  2196. * verification via get_user_pages. get_user() above
  2197. * does not guarantee R/W access. If that fails we
  2198. * give up and leave the futex locked.
  2199. */
  2200. if (cmpxchg_futex_value_locked(&nval, uaddr, uval, mval)) {
  2201. if (fault_in_user_writeable(uaddr))
  2202. return -1;
  2203. goto retry;
  2204. }
  2205. if (nval != uval)
  2206. goto retry;
  2207. /*
  2208. * Wake robust non-PI futexes here. The wakeup of
  2209. * PI futexes happens in exit_pi_state():
  2210. */
  2211. if (!pi && (uval & FUTEX_WAITERS))
  2212. futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);
  2213. }
  2214. return 0;
  2215. }
  2216. /*
  2217. * Fetch a robust-list pointer. Bit 0 signals PI futexes:
  2218. */
  2219. static inline int fetch_robust_entry(struct robust_list __user **entry,
  2220. struct robust_list __user * __user *head,
  2221. unsigned int *pi)
  2222. {
  2223. unsigned long uentry;
  2224. if (get_user(uentry, (unsigned long __user *)head))
  2225. return -EFAULT;
  2226. *entry = (void __user *)(uentry & ~1UL);
  2227. *pi = uentry & 1;
  2228. return 0;
  2229. }
  2230. /*
  2231. * Walk curr->robust_list (very carefully, it's a userspace list!)
  2232. * and mark any locks found there dead, and notify any waiters.
  2233. *
  2234. * We silently return on any sign of list-walking problem.
  2235. */
  2236. void exit_robust_list(struct task_struct *curr)
  2237. {
  2238. struct robust_list_head __user *head = curr->robust_list;
  2239. struct robust_list __user *entry, *next_entry, *pending;
  2240. unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
  2241. unsigned int uninitialized_var(next_pi);
  2242. unsigned long futex_offset;
  2243. int rc;
  2244. if (!futex_cmpxchg_enabled)
  2245. return;
  2246. /*
  2247. * Fetch the list head (which was registered earlier, via
  2248. * sys_set_robust_list()):
  2249. */
  2250. if (fetch_robust_entry(&entry, &head->list.next, &pi))
  2251. return;
  2252. /*
  2253. * Fetch the relative futex offset:
  2254. */
  2255. if (get_user(futex_offset, &head->futex_offset))
  2256. return;
  2257. /*
  2258. * Fetch any possibly pending lock-add first, and handle it
  2259. * if it exists:
  2260. */
  2261. if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
  2262. return;
  2263. next_entry = NULL; /* avoid warning with gcc */
  2264. while (entry != &head->list) {
  2265. /*
  2266. * Fetch the next entry in the list before calling
  2267. * handle_futex_death:
  2268. */
  2269. rc = fetch_robust_entry(&next_entry, &entry->next, &next_pi);
  2270. /*
  2271. * A pending lock might already be on the list, so
  2272. * don't process it twice:
  2273. */
  2274. if (entry != pending)
  2275. if (handle_futex_death((void __user *)entry + futex_offset,
  2276. curr, pi))
  2277. return;
  2278. if (rc)
  2279. return;
  2280. entry = next_entry;
  2281. pi = next_pi;
  2282. /*
  2283. * Avoid excessively long or circular lists:
  2284. */
  2285. if (!--limit)
  2286. break;
  2287. cond_resched();
  2288. }
  2289. if (pending)
  2290. handle_futex_death((void __user *)pending + futex_offset,
  2291. curr, pip);
  2292. }
  2293. long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
  2294. u32 __user *uaddr2, u32 val2, u32 val3)
  2295. {
  2296. int cmd = op & FUTEX_CMD_MASK;
  2297. unsigned int flags = 0;
  2298. if (!(op & FUTEX_PRIVATE_FLAG))
  2299. flags |= FLAGS_SHARED;
  2300. if (op & FUTEX_CLOCK_REALTIME) {
  2301. flags |= FLAGS_CLOCKRT;
  2302. if (cmd != FUTEX_WAIT_BITSET && cmd != FUTEX_WAIT_REQUEUE_PI)
  2303. return -ENOSYS;
  2304. }
  2305. switch (cmd) {
  2306. case FUTEX_LOCK_PI:
  2307. case FUTEX_UNLOCK_PI:
  2308. case FUTEX_TRYLOCK_PI:
  2309. case FUTEX_WAIT_REQUEUE_PI:
  2310. case FUTEX_CMP_REQUEUE_PI:
  2311. if (!futex_cmpxchg_enabled)
  2312. return -ENOSYS;
  2313. }
  2314. switch (cmd) {
  2315. case FUTEX_WAIT:
  2316. val3 = FUTEX_BITSET_MATCH_ANY;
  2317. case FUTEX_WAIT_BITSET:
  2318. return futex_wait(uaddr, flags, val, timeout, val3);
  2319. case FUTEX_WAKE:
  2320. val3 = FUTEX_BITSET_MATCH_ANY;
  2321. case FUTEX_WAKE_BITSET:
  2322. return futex_wake(uaddr, flags, val, val3);
  2323. case FUTEX_REQUEUE:
  2324. return futex_requeue(uaddr, flags, uaddr2, val, val2, NULL, 0);
  2325. case FUTEX_CMP_REQUEUE:
  2326. return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 0);
  2327. case FUTEX_WAKE_OP:
  2328. return futex_wake_op(uaddr, flags, uaddr2, val, val2, val3);
  2329. case FUTEX_LOCK_PI:
  2330. return futex_lock_pi(uaddr, flags, val, timeout, 0);
  2331. case FUTEX_UNLOCK_PI:
  2332. return futex_unlock_pi(uaddr, flags);
  2333. case FUTEX_TRYLOCK_PI:
  2334. return futex_lock_pi(uaddr, flags, 0, timeout, 1);
  2335. case FUTEX_WAIT_REQUEUE_PI:
  2336. val3 = FUTEX_BITSET_MATCH_ANY;
  2337. return futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
  2338. uaddr2);
  2339. case FUTEX_CMP_REQUEUE_PI:
  2340. return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
  2341. }
  2342. return -ENOSYS;
  2343. }
  2344. SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
  2345. struct timespec __user *, utime, u32 __user *, uaddr2,
  2346. u32, val3)
  2347. {
  2348. struct timespec ts;
  2349. ktime_t t, *tp = NULL;
  2350. u32 val2 = 0;
  2351. int cmd = op & FUTEX_CMD_MASK;
  2352. if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
  2353. cmd == FUTEX_WAIT_BITSET ||
  2354. cmd == FUTEX_WAIT_REQUEUE_PI)) {
  2355. if (copy_from_user(&ts, utime, sizeof(ts)) != 0)
  2356. return -EFAULT;
  2357. if (!timespec_valid(&ts))
  2358. return -EINVAL;
  2359. t = timespec_to_ktime(ts);
  2360. if (cmd == FUTEX_WAIT)
  2361. t = ktime_add_safe(ktime_get(), t);
  2362. tp = &t;
  2363. }
  2364. /*
  2365. * requeue parameter in 'utime' if cmd == FUTEX_*_REQUEUE_*.
  2366. * number of waiters to wake in 'utime' if cmd == FUTEX_WAKE_OP.
  2367. */
  2368. if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||
  2369. cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
  2370. val2 = (u32) (unsigned long) utime;
  2371. return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
  2372. }
  2373. static int __init futex_init(void)
  2374. {
  2375. u32 curval;
  2376. int i;
  2377. /*
  2378. * This will fail and we want it. Some arch implementations do
  2379. * runtime detection of the futex_atomic_cmpxchg_inatomic()
  2380. * functionality. We want to know that before we call in any
  2381. * of the complex code paths. Also we want to prevent
  2382. * registration of robust lists in that case. NULL is
  2383. * guaranteed to fault and we get -EFAULT on functional
  2384. * implementation, the non-functional ones will return
  2385. * -ENOSYS.
  2386. */
  2387. if (cmpxchg_futex_value_locked(&curval, NULL, 0, 0) == -EFAULT)
  2388. futex_cmpxchg_enabled = 1;
  2389. for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
  2390. plist_head_init(&futex_queues[i].chain);
  2391. spin_lock_init(&futex_queues[i].lock);
  2392. }
  2393. return 0;
  2394. }
  2395. __initcall(futex_init);