futex.c 44 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879
  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. * Thanks to Ben LaHaise for yelling "hashed waitqueues" loudly
  20. * enough at me, Linus for the original (flawed) idea, Matthew
  21. * Kirkwood for proof-of-concept implementation.
  22. *
  23. * "The futexes are also cursed."
  24. * "But they come in a choice of three flavours!"
  25. *
  26. * This program is free software; you can redistribute it and/or modify
  27. * it under the terms of the GNU General Public License as published by
  28. * the Free Software Foundation; either version 2 of the License, or
  29. * (at your option) any later version.
  30. *
  31. * This program is distributed in the hope that it will be useful,
  32. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  34. * GNU General Public License for more details.
  35. *
  36. * You should have received a copy of the GNU General Public License
  37. * along with this program; if not, write to the Free Software
  38. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  39. */
  40. #include <linux/slab.h>
  41. #include <linux/poll.h>
  42. #include <linux/fs.h>
  43. #include <linux/file.h>
  44. #include <linux/jhash.h>
  45. #include <linux/init.h>
  46. #include <linux/futex.h>
  47. #include <linux/mount.h>
  48. #include <linux/pagemap.h>
  49. #include <linux/syscalls.h>
  50. #include <linux/signal.h>
  51. #include <asm/futex.h>
  52. #include "rtmutex_common.h"
  53. #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
  54. /*
  55. * Futexes are matched on equal values of this key.
  56. * The key type depends on whether it's a shared or private mapping.
  57. * Don't rearrange members without looking at hash_futex().
  58. *
  59. * offset is aligned to a multiple of sizeof(u32) (== 4) by definition.
  60. * We set bit 0 to indicate if it's an inode-based key.
  61. */
  62. union futex_key {
  63. struct {
  64. unsigned long pgoff;
  65. struct inode *inode;
  66. int offset;
  67. } shared;
  68. struct {
  69. unsigned long address;
  70. struct mm_struct *mm;
  71. int offset;
  72. } private;
  73. struct {
  74. unsigned long word;
  75. void *ptr;
  76. int offset;
  77. } both;
  78. };
  79. /*
  80. * Priority Inheritance state:
  81. */
  82. struct futex_pi_state {
  83. /*
  84. * list of 'owned' pi_state instances - these have to be
  85. * cleaned up in do_exit() if the task exits prematurely:
  86. */
  87. struct list_head list;
  88. /*
  89. * The PI object:
  90. */
  91. struct rt_mutex pi_mutex;
  92. struct task_struct *owner;
  93. atomic_t refcount;
  94. union futex_key key;
  95. };
  96. /*
  97. * We use this hashed waitqueue instead of a normal wait_queue_t, so
  98. * we can wake only the relevant ones (hashed queues may be shared).
  99. *
  100. * A futex_q has a woken state, just like tasks have TASK_RUNNING.
  101. * It is considered woken when list_empty(&q->list) || q->lock_ptr == 0.
  102. * The order of wakup is always to make the first condition true, then
  103. * wake up q->waiters, then make the second condition true.
  104. */
  105. struct futex_q {
  106. struct list_head list;
  107. wait_queue_head_t waiters;
  108. /* Which hash list lock to use: */
  109. spinlock_t *lock_ptr;
  110. /* Key which the futex is hashed on: */
  111. union futex_key key;
  112. /* For fd, sigio sent using these: */
  113. int fd;
  114. struct file *filp;
  115. /* Optional priority inheritance state: */
  116. struct futex_pi_state *pi_state;
  117. struct task_struct *task;
  118. };
  119. /*
  120. * Split the global futex_lock into every hash list lock.
  121. */
  122. struct futex_hash_bucket {
  123. spinlock_t lock;
  124. struct list_head chain;
  125. };
  126. static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
  127. /* Futex-fs vfsmount entry: */
  128. static struct vfsmount *futex_mnt;
  129. /*
  130. * We hash on the keys returned from get_futex_key (see below).
  131. */
  132. static struct futex_hash_bucket *hash_futex(union futex_key *key)
  133. {
  134. u32 hash = jhash2((u32*)&key->both.word,
  135. (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
  136. key->both.offset);
  137. return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
  138. }
  139. /*
  140. * Return 1 if two futex_keys are equal, 0 otherwise.
  141. */
  142. static inline int match_futex(union futex_key *key1, union futex_key *key2)
  143. {
  144. return (key1->both.word == key2->both.word
  145. && key1->both.ptr == key2->both.ptr
  146. && key1->both.offset == key2->both.offset);
  147. }
  148. /*
  149. * Get parameters which are the keys for a futex.
  150. *
  151. * For shared mappings, it's (page->index, vma->vm_file->f_path.dentry->d_inode,
  152. * offset_within_page). For private mappings, it's (uaddr, current->mm).
  153. * We can usually work out the index without swapping in the page.
  154. *
  155. * Returns: 0, or negative error code.
  156. * The key words are stored in *key on success.
  157. *
  158. * Should be called with &current->mm->mmap_sem but NOT any spinlocks.
  159. */
  160. static int get_futex_key(u32 __user *uaddr, union futex_key *key)
  161. {
  162. unsigned long address = (unsigned long)uaddr;
  163. struct mm_struct *mm = current->mm;
  164. struct vm_area_struct *vma;
  165. struct page *page;
  166. int err;
  167. /*
  168. * The futex address must be "naturally" aligned.
  169. */
  170. key->both.offset = address % PAGE_SIZE;
  171. if (unlikely((key->both.offset % sizeof(u32)) != 0))
  172. return -EINVAL;
  173. address -= key->both.offset;
  174. /*
  175. * The futex is hashed differently depending on whether
  176. * it's in a shared or private mapping. So check vma first.
  177. */
  178. vma = find_extend_vma(mm, address);
  179. if (unlikely(!vma))
  180. return -EFAULT;
  181. /*
  182. * Permissions.
  183. */
  184. if (unlikely((vma->vm_flags & (VM_IO|VM_READ)) != VM_READ))
  185. return (vma->vm_flags & VM_IO) ? -EPERM : -EACCES;
  186. /*
  187. * Private mappings are handled in a simple way.
  188. *
  189. * NOTE: When userspace waits on a MAP_SHARED mapping, even if
  190. * it's a read-only handle, it's expected that futexes attach to
  191. * the object not the particular process. Therefore we use
  192. * VM_MAYSHARE here, not VM_SHARED which is restricted to shared
  193. * mappings of _writable_ handles.
  194. */
  195. if (likely(!(vma->vm_flags & VM_MAYSHARE))) {
  196. key->private.mm = mm;
  197. key->private.address = address;
  198. return 0;
  199. }
  200. /*
  201. * Linear file mappings are also simple.
  202. */
  203. key->shared.inode = vma->vm_file->f_path.dentry->d_inode;
  204. key->both.offset++; /* Bit 0 of offset indicates inode-based key. */
  205. if (likely(!(vma->vm_flags & VM_NONLINEAR))) {
  206. key->shared.pgoff = (((address - vma->vm_start) >> PAGE_SHIFT)
  207. + vma->vm_pgoff);
  208. return 0;
  209. }
  210. /*
  211. * We could walk the page table to read the non-linear
  212. * pte, and get the page index without fetching the page
  213. * from swap. But that's a lot of code to duplicate here
  214. * for a rare case, so we simply fetch the page.
  215. */
  216. err = get_user_pages(current, mm, address, 1, 0, 0, &page, NULL);
  217. if (err >= 0) {
  218. key->shared.pgoff =
  219. page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
  220. put_page(page);
  221. return 0;
  222. }
  223. return err;
  224. }
  225. /*
  226. * Take a reference to the resource addressed by a key.
  227. * Can be called while holding spinlocks.
  228. *
  229. * NOTE: mmap_sem MUST be held between get_futex_key() and calling this
  230. * function, if it is called at all. mmap_sem keeps key->shared.inode valid.
  231. */
  232. static inline void get_key_refs(union futex_key *key)
  233. {
  234. if (key->both.ptr != 0) {
  235. if (key->both.offset & 1)
  236. atomic_inc(&key->shared.inode->i_count);
  237. else
  238. atomic_inc(&key->private.mm->mm_count);
  239. }
  240. }
  241. /*
  242. * Drop a reference to the resource addressed by a key.
  243. * The hash bucket spinlock must not be held.
  244. */
  245. static void drop_key_refs(union futex_key *key)
  246. {
  247. if (key->both.ptr != 0) {
  248. if (key->both.offset & 1)
  249. iput(key->shared.inode);
  250. else
  251. mmdrop(key->private.mm);
  252. }
  253. }
  254. static inline int get_futex_value_locked(u32 *dest, u32 __user *from)
  255. {
  256. int ret;
  257. pagefault_disable();
  258. ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
  259. pagefault_enable();
  260. return ret ? -EFAULT : 0;
  261. }
  262. /*
  263. * Fault handling. Called with current->mm->mmap_sem held.
  264. */
  265. static int futex_handle_fault(unsigned long address, int attempt)
  266. {
  267. struct vm_area_struct * vma;
  268. struct mm_struct *mm = current->mm;
  269. if (attempt > 2 || !(vma = find_vma(mm, address)) ||
  270. vma->vm_start > address || !(vma->vm_flags & VM_WRITE))
  271. return -EFAULT;
  272. switch (handle_mm_fault(mm, vma, address, 1)) {
  273. case VM_FAULT_MINOR:
  274. current->min_flt++;
  275. break;
  276. case VM_FAULT_MAJOR:
  277. current->maj_flt++;
  278. break;
  279. default:
  280. return -EFAULT;
  281. }
  282. return 0;
  283. }
  284. /*
  285. * PI code:
  286. */
  287. static int refill_pi_state_cache(void)
  288. {
  289. struct futex_pi_state *pi_state;
  290. if (likely(current->pi_state_cache))
  291. return 0;
  292. pi_state = kzalloc(sizeof(*pi_state), GFP_KERNEL);
  293. if (!pi_state)
  294. return -ENOMEM;
  295. INIT_LIST_HEAD(&pi_state->list);
  296. /* pi_mutex gets initialized later */
  297. pi_state->owner = NULL;
  298. atomic_set(&pi_state->refcount, 1);
  299. current->pi_state_cache = pi_state;
  300. return 0;
  301. }
  302. static struct futex_pi_state * alloc_pi_state(void)
  303. {
  304. struct futex_pi_state *pi_state = current->pi_state_cache;
  305. WARN_ON(!pi_state);
  306. current->pi_state_cache = NULL;
  307. return pi_state;
  308. }
  309. static void free_pi_state(struct futex_pi_state *pi_state)
  310. {
  311. if (!atomic_dec_and_test(&pi_state->refcount))
  312. return;
  313. /*
  314. * If pi_state->owner is NULL, the owner is most probably dying
  315. * and has cleaned up the pi_state already
  316. */
  317. if (pi_state->owner) {
  318. spin_lock_irq(&pi_state->owner->pi_lock);
  319. list_del_init(&pi_state->list);
  320. spin_unlock_irq(&pi_state->owner->pi_lock);
  321. rt_mutex_proxy_unlock(&pi_state->pi_mutex, pi_state->owner);
  322. }
  323. if (current->pi_state_cache)
  324. kfree(pi_state);
  325. else {
  326. /*
  327. * pi_state->list is already empty.
  328. * clear pi_state->owner.
  329. * refcount is at 0 - put it back to 1.
  330. */
  331. pi_state->owner = NULL;
  332. atomic_set(&pi_state->refcount, 1);
  333. current->pi_state_cache = pi_state;
  334. }
  335. }
  336. /*
  337. * Look up the task based on what TID userspace gave us.
  338. * We dont trust it.
  339. */
  340. static struct task_struct * futex_find_get_task(pid_t pid)
  341. {
  342. struct task_struct *p;
  343. rcu_read_lock();
  344. p = find_task_by_pid(pid);
  345. if (!p)
  346. goto out_unlock;
  347. if ((current->euid != p->euid) && (current->euid != p->uid)) {
  348. p = NULL;
  349. goto out_unlock;
  350. }
  351. if (p->exit_state != 0) {
  352. p = NULL;
  353. goto out_unlock;
  354. }
  355. get_task_struct(p);
  356. out_unlock:
  357. rcu_read_unlock();
  358. return p;
  359. }
  360. /*
  361. * This task is holding PI mutexes at exit time => bad.
  362. * Kernel cleans up PI-state, but userspace is likely hosed.
  363. * (Robust-futex cleanup is separate and might save the day for userspace.)
  364. */
  365. void exit_pi_state_list(struct task_struct *curr)
  366. {
  367. struct list_head *next, *head = &curr->pi_state_list;
  368. struct futex_pi_state *pi_state;
  369. struct futex_hash_bucket *hb;
  370. union futex_key key;
  371. /*
  372. * We are a ZOMBIE and nobody can enqueue itself on
  373. * pi_state_list anymore, but we have to be careful
  374. * versus waiters unqueueing themselves:
  375. */
  376. spin_lock_irq(&curr->pi_lock);
  377. while (!list_empty(head)) {
  378. next = head->next;
  379. pi_state = list_entry(next, struct futex_pi_state, list);
  380. key = pi_state->key;
  381. hb = hash_futex(&key);
  382. spin_unlock_irq(&curr->pi_lock);
  383. spin_lock(&hb->lock);
  384. spin_lock_irq(&curr->pi_lock);
  385. /*
  386. * We dropped the pi-lock, so re-check whether this
  387. * task still owns the PI-state:
  388. */
  389. if (head->next != next) {
  390. spin_unlock(&hb->lock);
  391. continue;
  392. }
  393. WARN_ON(pi_state->owner != curr);
  394. WARN_ON(list_empty(&pi_state->list));
  395. list_del_init(&pi_state->list);
  396. pi_state->owner = NULL;
  397. spin_unlock_irq(&curr->pi_lock);
  398. rt_mutex_unlock(&pi_state->pi_mutex);
  399. spin_unlock(&hb->lock);
  400. spin_lock_irq(&curr->pi_lock);
  401. }
  402. spin_unlock_irq(&curr->pi_lock);
  403. }
  404. static int
  405. lookup_pi_state(u32 uval, struct futex_hash_bucket *hb, struct futex_q *me)
  406. {
  407. struct futex_pi_state *pi_state = NULL;
  408. struct futex_q *this, *next;
  409. struct list_head *head;
  410. struct task_struct *p;
  411. pid_t pid;
  412. head = &hb->chain;
  413. list_for_each_entry_safe(this, next, head, list) {
  414. if (match_futex(&this->key, &me->key)) {
  415. /*
  416. * Another waiter already exists - bump up
  417. * the refcount and return its pi_state:
  418. */
  419. pi_state = this->pi_state;
  420. /*
  421. * Userspace might have messed up non PI and PI futexes
  422. */
  423. if (unlikely(!pi_state))
  424. return -EINVAL;
  425. WARN_ON(!atomic_read(&pi_state->refcount));
  426. atomic_inc(&pi_state->refcount);
  427. me->pi_state = pi_state;
  428. return 0;
  429. }
  430. }
  431. /*
  432. * We are the first waiter - try to look up the real owner and attach
  433. * the new pi_state to it, but bail out when the owner died bit is set
  434. * and TID = 0:
  435. */
  436. pid = uval & FUTEX_TID_MASK;
  437. if (!pid && (uval & FUTEX_OWNER_DIED))
  438. return -ESRCH;
  439. p = futex_find_get_task(pid);
  440. if (!p)
  441. return -ESRCH;
  442. pi_state = alloc_pi_state();
  443. /*
  444. * Initialize the pi_mutex in locked state and make 'p'
  445. * the owner of it:
  446. */
  447. rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
  448. /* Store the key for possible exit cleanups: */
  449. pi_state->key = me->key;
  450. spin_lock_irq(&p->pi_lock);
  451. WARN_ON(!list_empty(&pi_state->list));
  452. list_add(&pi_state->list, &p->pi_state_list);
  453. pi_state->owner = p;
  454. spin_unlock_irq(&p->pi_lock);
  455. put_task_struct(p);
  456. me->pi_state = pi_state;
  457. return 0;
  458. }
  459. /*
  460. * The hash bucket lock must be held when this is called.
  461. * Afterwards, the futex_q must not be accessed.
  462. */
  463. static void wake_futex(struct futex_q *q)
  464. {
  465. list_del_init(&q->list);
  466. if (q->filp)
  467. send_sigio(&q->filp->f_owner, q->fd, POLL_IN);
  468. /*
  469. * The lock in wake_up_all() is a crucial memory barrier after the
  470. * list_del_init() and also before assigning to q->lock_ptr.
  471. */
  472. wake_up_all(&q->waiters);
  473. /*
  474. * The waiting task can free the futex_q as soon as this is written,
  475. * without taking any locks. This must come last.
  476. *
  477. * A memory barrier is required here to prevent the following store
  478. * to lock_ptr from getting ahead of the wakeup. Clearing the lock
  479. * at the end of wake_up_all() does not prevent this store from
  480. * moving.
  481. */
  482. smp_wmb();
  483. q->lock_ptr = NULL;
  484. }
  485. static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)
  486. {
  487. struct task_struct *new_owner;
  488. struct futex_pi_state *pi_state = this->pi_state;
  489. u32 curval, newval;
  490. if (!pi_state)
  491. return -EINVAL;
  492. spin_lock(&pi_state->pi_mutex.wait_lock);
  493. new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
  494. /*
  495. * This happens when we have stolen the lock and the original
  496. * pending owner did not enqueue itself back on the rt_mutex.
  497. * Thats not a tragedy. We know that way, that a lock waiter
  498. * is on the fly. We make the futex_q waiter the pending owner.
  499. */
  500. if (!new_owner)
  501. new_owner = this->task;
  502. /*
  503. * We pass it to the next owner. (The WAITERS bit is always
  504. * kept enabled while there is PI state around. We must also
  505. * preserve the owner died bit.)
  506. */
  507. if (!(uval & FUTEX_OWNER_DIED)) {
  508. newval = FUTEX_WAITERS | new_owner->pid;
  509. pagefault_disable();
  510. curval = futex_atomic_cmpxchg_inatomic(uaddr, uval, newval);
  511. pagefault_enable();
  512. if (curval == -EFAULT)
  513. return -EFAULT;
  514. if (curval != uval)
  515. return -EINVAL;
  516. }
  517. spin_lock_irq(&pi_state->owner->pi_lock);
  518. WARN_ON(list_empty(&pi_state->list));
  519. list_del_init(&pi_state->list);
  520. spin_unlock_irq(&pi_state->owner->pi_lock);
  521. spin_lock_irq(&new_owner->pi_lock);
  522. WARN_ON(!list_empty(&pi_state->list));
  523. list_add(&pi_state->list, &new_owner->pi_state_list);
  524. pi_state->owner = new_owner;
  525. spin_unlock_irq(&new_owner->pi_lock);
  526. spin_unlock(&pi_state->pi_mutex.wait_lock);
  527. rt_mutex_unlock(&pi_state->pi_mutex);
  528. return 0;
  529. }
  530. static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
  531. {
  532. u32 oldval;
  533. /*
  534. * There is no waiter, so we unlock the futex. The owner died
  535. * bit has not to be preserved here. We are the owner:
  536. */
  537. pagefault_disable();
  538. oldval = futex_atomic_cmpxchg_inatomic(uaddr, uval, 0);
  539. pagefault_enable();
  540. if (oldval == -EFAULT)
  541. return oldval;
  542. if (oldval != uval)
  543. return -EAGAIN;
  544. return 0;
  545. }
  546. /*
  547. * Express the locking dependencies for lockdep:
  548. */
  549. static inline void
  550. double_lock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
  551. {
  552. if (hb1 <= hb2) {
  553. spin_lock(&hb1->lock);
  554. if (hb1 < hb2)
  555. spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
  556. } else { /* hb1 > hb2 */
  557. spin_lock(&hb2->lock);
  558. spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
  559. }
  560. }
  561. /*
  562. * Wake up all waiters hashed on the physical page that is mapped
  563. * to this virtual address:
  564. */
  565. static int futex_wake(u32 __user *uaddr, int nr_wake)
  566. {
  567. struct futex_hash_bucket *hb;
  568. struct futex_q *this, *next;
  569. struct list_head *head;
  570. union futex_key key;
  571. int ret;
  572. down_read(&current->mm->mmap_sem);
  573. ret = get_futex_key(uaddr, &key);
  574. if (unlikely(ret != 0))
  575. goto out;
  576. hb = hash_futex(&key);
  577. spin_lock(&hb->lock);
  578. head = &hb->chain;
  579. list_for_each_entry_safe(this, next, head, list) {
  580. if (match_futex (&this->key, &key)) {
  581. if (this->pi_state) {
  582. ret = -EINVAL;
  583. break;
  584. }
  585. wake_futex(this);
  586. if (++ret >= nr_wake)
  587. break;
  588. }
  589. }
  590. spin_unlock(&hb->lock);
  591. out:
  592. up_read(&current->mm->mmap_sem);
  593. return ret;
  594. }
  595. /*
  596. * Wake up all waiters hashed on the physical page that is mapped
  597. * to this virtual address:
  598. */
  599. static int
  600. futex_wake_op(u32 __user *uaddr1, u32 __user *uaddr2,
  601. int nr_wake, int nr_wake2, int op)
  602. {
  603. union futex_key key1, key2;
  604. struct futex_hash_bucket *hb1, *hb2;
  605. struct list_head *head;
  606. struct futex_q *this, *next;
  607. int ret, op_ret, attempt = 0;
  608. retryfull:
  609. down_read(&current->mm->mmap_sem);
  610. ret = get_futex_key(uaddr1, &key1);
  611. if (unlikely(ret != 0))
  612. goto out;
  613. ret = get_futex_key(uaddr2, &key2);
  614. if (unlikely(ret != 0))
  615. goto out;
  616. hb1 = hash_futex(&key1);
  617. hb2 = hash_futex(&key2);
  618. retry:
  619. double_lock_hb(hb1, hb2);
  620. op_ret = futex_atomic_op_inuser(op, uaddr2);
  621. if (unlikely(op_ret < 0)) {
  622. u32 dummy;
  623. spin_unlock(&hb1->lock);
  624. if (hb1 != hb2)
  625. spin_unlock(&hb2->lock);
  626. #ifndef CONFIG_MMU
  627. /*
  628. * we don't get EFAULT from MMU faults if we don't have an MMU,
  629. * but we might get them from range checking
  630. */
  631. ret = op_ret;
  632. goto out;
  633. #endif
  634. if (unlikely(op_ret != -EFAULT)) {
  635. ret = op_ret;
  636. goto out;
  637. }
  638. /*
  639. * futex_atomic_op_inuser needs to both read and write
  640. * *(int __user *)uaddr2, but we can't modify it
  641. * non-atomically. Therefore, if get_user below is not
  642. * enough, we need to handle the fault ourselves, while
  643. * still holding the mmap_sem.
  644. */
  645. if (attempt++) {
  646. if (futex_handle_fault((unsigned long)uaddr2,
  647. attempt)) {
  648. ret = -EFAULT;
  649. goto out;
  650. }
  651. goto retry;
  652. }
  653. /*
  654. * If we would have faulted, release mmap_sem,
  655. * fault it in and start all over again.
  656. */
  657. up_read(&current->mm->mmap_sem);
  658. ret = get_user(dummy, uaddr2);
  659. if (ret)
  660. return ret;
  661. goto retryfull;
  662. }
  663. head = &hb1->chain;
  664. list_for_each_entry_safe(this, next, head, list) {
  665. if (match_futex (&this->key, &key1)) {
  666. wake_futex(this);
  667. if (++ret >= nr_wake)
  668. break;
  669. }
  670. }
  671. if (op_ret > 0) {
  672. head = &hb2->chain;
  673. op_ret = 0;
  674. list_for_each_entry_safe(this, next, head, list) {
  675. if (match_futex (&this->key, &key2)) {
  676. wake_futex(this);
  677. if (++op_ret >= nr_wake2)
  678. break;
  679. }
  680. }
  681. ret += op_ret;
  682. }
  683. spin_unlock(&hb1->lock);
  684. if (hb1 != hb2)
  685. spin_unlock(&hb2->lock);
  686. out:
  687. up_read(&current->mm->mmap_sem);
  688. return ret;
  689. }
  690. /*
  691. * Requeue all waiters hashed on one physical page to another
  692. * physical page.
  693. */
  694. static int futex_requeue(u32 __user *uaddr1, u32 __user *uaddr2,
  695. int nr_wake, int nr_requeue, u32 *cmpval)
  696. {
  697. union futex_key key1, key2;
  698. struct futex_hash_bucket *hb1, *hb2;
  699. struct list_head *head1;
  700. struct futex_q *this, *next;
  701. int ret, drop_count = 0;
  702. retry:
  703. down_read(&current->mm->mmap_sem);
  704. ret = get_futex_key(uaddr1, &key1);
  705. if (unlikely(ret != 0))
  706. goto out;
  707. ret = get_futex_key(uaddr2, &key2);
  708. if (unlikely(ret != 0))
  709. goto out;
  710. hb1 = hash_futex(&key1);
  711. hb2 = hash_futex(&key2);
  712. double_lock_hb(hb1, hb2);
  713. if (likely(cmpval != NULL)) {
  714. u32 curval;
  715. ret = get_futex_value_locked(&curval, uaddr1);
  716. if (unlikely(ret)) {
  717. spin_unlock(&hb1->lock);
  718. if (hb1 != hb2)
  719. spin_unlock(&hb2->lock);
  720. /*
  721. * If we would have faulted, release mmap_sem, fault
  722. * it in and start all over again.
  723. */
  724. up_read(&current->mm->mmap_sem);
  725. ret = get_user(curval, uaddr1);
  726. if (!ret)
  727. goto retry;
  728. return ret;
  729. }
  730. if (curval != *cmpval) {
  731. ret = -EAGAIN;
  732. goto out_unlock;
  733. }
  734. }
  735. head1 = &hb1->chain;
  736. list_for_each_entry_safe(this, next, head1, list) {
  737. if (!match_futex (&this->key, &key1))
  738. continue;
  739. if (++ret <= nr_wake) {
  740. wake_futex(this);
  741. } else {
  742. /*
  743. * If key1 and key2 hash to the same bucket, no need to
  744. * requeue.
  745. */
  746. if (likely(head1 != &hb2->chain)) {
  747. list_move_tail(&this->list, &hb2->chain);
  748. this->lock_ptr = &hb2->lock;
  749. }
  750. this->key = key2;
  751. get_key_refs(&key2);
  752. drop_count++;
  753. if (ret - nr_wake >= nr_requeue)
  754. break;
  755. }
  756. }
  757. out_unlock:
  758. spin_unlock(&hb1->lock);
  759. if (hb1 != hb2)
  760. spin_unlock(&hb2->lock);
  761. /* drop_key_refs() must be called outside the spinlocks. */
  762. while (--drop_count >= 0)
  763. drop_key_refs(&key1);
  764. out:
  765. up_read(&current->mm->mmap_sem);
  766. return ret;
  767. }
  768. /* The key must be already stored in q->key. */
  769. static inline struct futex_hash_bucket *
  770. queue_lock(struct futex_q *q, int fd, struct file *filp)
  771. {
  772. struct futex_hash_bucket *hb;
  773. q->fd = fd;
  774. q->filp = filp;
  775. init_waitqueue_head(&q->waiters);
  776. get_key_refs(&q->key);
  777. hb = hash_futex(&q->key);
  778. q->lock_ptr = &hb->lock;
  779. spin_lock(&hb->lock);
  780. return hb;
  781. }
  782. static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
  783. {
  784. list_add_tail(&q->list, &hb->chain);
  785. q->task = current;
  786. spin_unlock(&hb->lock);
  787. }
  788. static inline void
  789. queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
  790. {
  791. spin_unlock(&hb->lock);
  792. drop_key_refs(&q->key);
  793. }
  794. /*
  795. * queue_me and unqueue_me must be called as a pair, each
  796. * exactly once. They are called with the hashed spinlock held.
  797. */
  798. /* The key must be already stored in q->key. */
  799. static void queue_me(struct futex_q *q, int fd, struct file *filp)
  800. {
  801. struct futex_hash_bucket *hb;
  802. hb = queue_lock(q, fd, filp);
  803. __queue_me(q, hb);
  804. }
  805. /* Return 1 if we were still queued (ie. 0 means we were woken) */
  806. static int unqueue_me(struct futex_q *q)
  807. {
  808. spinlock_t *lock_ptr;
  809. int ret = 0;
  810. /* In the common case we don't take the spinlock, which is nice. */
  811. retry:
  812. lock_ptr = q->lock_ptr;
  813. barrier();
  814. if (lock_ptr != 0) {
  815. spin_lock(lock_ptr);
  816. /*
  817. * q->lock_ptr can change between reading it and
  818. * spin_lock(), causing us to take the wrong lock. This
  819. * corrects the race condition.
  820. *
  821. * Reasoning goes like this: if we have the wrong lock,
  822. * q->lock_ptr must have changed (maybe several times)
  823. * between reading it and the spin_lock(). It can
  824. * change again after the spin_lock() but only if it was
  825. * already changed before the spin_lock(). It cannot,
  826. * however, change back to the original value. Therefore
  827. * we can detect whether we acquired the correct lock.
  828. */
  829. if (unlikely(lock_ptr != q->lock_ptr)) {
  830. spin_unlock(lock_ptr);
  831. goto retry;
  832. }
  833. WARN_ON(list_empty(&q->list));
  834. list_del(&q->list);
  835. BUG_ON(q->pi_state);
  836. spin_unlock(lock_ptr);
  837. ret = 1;
  838. }
  839. drop_key_refs(&q->key);
  840. return ret;
  841. }
  842. /*
  843. * PI futexes can not be requeued and must remove themself from the
  844. * hash bucket. The hash bucket lock is held on entry and dropped here.
  845. */
  846. static void unqueue_me_pi(struct futex_q *q, struct futex_hash_bucket *hb)
  847. {
  848. WARN_ON(list_empty(&q->list));
  849. list_del(&q->list);
  850. BUG_ON(!q->pi_state);
  851. free_pi_state(q->pi_state);
  852. q->pi_state = NULL;
  853. spin_unlock(&hb->lock);
  854. drop_key_refs(&q->key);
  855. }
  856. static int futex_wait(u32 __user *uaddr, u32 val, unsigned long time)
  857. {
  858. struct task_struct *curr = current;
  859. DECLARE_WAITQUEUE(wait, curr);
  860. struct futex_hash_bucket *hb;
  861. struct futex_q q;
  862. u32 uval;
  863. int ret;
  864. q.pi_state = NULL;
  865. retry:
  866. down_read(&curr->mm->mmap_sem);
  867. ret = get_futex_key(uaddr, &q.key);
  868. if (unlikely(ret != 0))
  869. goto out_release_sem;
  870. hb = queue_lock(&q, -1, NULL);
  871. /*
  872. * Access the page AFTER the futex is queued.
  873. * Order is important:
  874. *
  875. * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val);
  876. * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); }
  877. *
  878. * The basic logical guarantee of a futex is that it blocks ONLY
  879. * if cond(var) is known to be true at the time of blocking, for
  880. * any cond. If we queued after testing *uaddr, that would open
  881. * a race condition where we could block indefinitely with
  882. * cond(var) false, which would violate the guarantee.
  883. *
  884. * A consequence is that futex_wait() can return zero and absorb
  885. * a wakeup when *uaddr != val on entry to the syscall. This is
  886. * rare, but normal.
  887. *
  888. * We hold the mmap semaphore, so the mapping cannot have changed
  889. * since we looked it up in get_futex_key.
  890. */
  891. ret = get_futex_value_locked(&uval, uaddr);
  892. if (unlikely(ret)) {
  893. queue_unlock(&q, hb);
  894. /*
  895. * If we would have faulted, release mmap_sem, fault it in and
  896. * start all over again.
  897. */
  898. up_read(&curr->mm->mmap_sem);
  899. ret = get_user(uval, uaddr);
  900. if (!ret)
  901. goto retry;
  902. return ret;
  903. }
  904. ret = -EWOULDBLOCK;
  905. if (uval != val)
  906. goto out_unlock_release_sem;
  907. /* Only actually queue if *uaddr contained val. */
  908. __queue_me(&q, hb);
  909. /*
  910. * Now the futex is queued and we have checked the data, we
  911. * don't want to hold mmap_sem while we sleep.
  912. */
  913. up_read(&curr->mm->mmap_sem);
  914. /*
  915. * There might have been scheduling since the queue_me(), as we
  916. * cannot hold a spinlock across the get_user() in case it
  917. * faults, and we cannot just set TASK_INTERRUPTIBLE state when
  918. * queueing ourselves into the futex hash. This code thus has to
  919. * rely on the futex_wake() code removing us from hash when it
  920. * wakes us up.
  921. */
  922. /* add_wait_queue is the barrier after __set_current_state. */
  923. __set_current_state(TASK_INTERRUPTIBLE);
  924. add_wait_queue(&q.waiters, &wait);
  925. /*
  926. * !list_empty() is safe here without any lock.
  927. * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
  928. */
  929. if (likely(!list_empty(&q.list)))
  930. time = schedule_timeout(time);
  931. __set_current_state(TASK_RUNNING);
  932. /*
  933. * NOTE: we don't remove ourselves from the waitqueue because
  934. * we are the only user of it.
  935. */
  936. /* If we were woken (and unqueued), we succeeded, whatever. */
  937. if (!unqueue_me(&q))
  938. return 0;
  939. if (time == 0)
  940. return -ETIMEDOUT;
  941. /*
  942. * We expect signal_pending(current), but another thread may
  943. * have handled it for us already.
  944. */
  945. return -EINTR;
  946. out_unlock_release_sem:
  947. queue_unlock(&q, hb);
  948. out_release_sem:
  949. up_read(&curr->mm->mmap_sem);
  950. return ret;
  951. }
  952. /*
  953. * Userspace tried a 0 -> TID atomic transition of the futex value
  954. * and failed. The kernel side here does the whole locking operation:
  955. * if there are waiters then it will block, it does PI, etc. (Due to
  956. * races the kernel might see a 0 value of the futex too.)
  957. */
  958. static int futex_lock_pi(u32 __user *uaddr, int detect, unsigned long sec,
  959. long nsec, int trylock)
  960. {
  961. struct hrtimer_sleeper timeout, *to = NULL;
  962. struct task_struct *curr = current;
  963. struct futex_hash_bucket *hb;
  964. u32 uval, newval, curval;
  965. struct futex_q q;
  966. int ret, attempt = 0;
  967. if (refill_pi_state_cache())
  968. return -ENOMEM;
  969. if (sec != MAX_SCHEDULE_TIMEOUT) {
  970. to = &timeout;
  971. hrtimer_init(&to->timer, CLOCK_REALTIME, HRTIMER_MODE_ABS);
  972. hrtimer_init_sleeper(to, current);
  973. to->timer.expires = ktime_set(sec, nsec);
  974. }
  975. q.pi_state = NULL;
  976. retry:
  977. down_read(&curr->mm->mmap_sem);
  978. ret = get_futex_key(uaddr, &q.key);
  979. if (unlikely(ret != 0))
  980. goto out_release_sem;
  981. hb = queue_lock(&q, -1, NULL);
  982. retry_locked:
  983. /*
  984. * To avoid races, we attempt to take the lock here again
  985. * (by doing a 0 -> TID atomic cmpxchg), while holding all
  986. * the locks. It will most likely not succeed.
  987. */
  988. newval = current->pid;
  989. pagefault_disable();
  990. curval = futex_atomic_cmpxchg_inatomic(uaddr, 0, newval);
  991. pagefault_enable();
  992. if (unlikely(curval == -EFAULT))
  993. goto uaddr_faulted;
  994. /* We own the lock already */
  995. if (unlikely((curval & FUTEX_TID_MASK) == current->pid)) {
  996. if (!detect && 0)
  997. force_sig(SIGKILL, current);
  998. ret = -EDEADLK;
  999. goto out_unlock_release_sem;
  1000. }
  1001. /*
  1002. * Surprise - we got the lock. Just return
  1003. * to userspace:
  1004. */
  1005. if (unlikely(!curval))
  1006. goto out_unlock_release_sem;
  1007. uval = curval;
  1008. newval = uval | FUTEX_WAITERS;
  1009. pagefault_disable();
  1010. curval = futex_atomic_cmpxchg_inatomic(uaddr, uval, newval);
  1011. pagefault_enable();
  1012. if (unlikely(curval == -EFAULT))
  1013. goto uaddr_faulted;
  1014. if (unlikely(curval != uval))
  1015. goto retry_locked;
  1016. /*
  1017. * We dont have the lock. Look up the PI state (or create it if
  1018. * we are the first waiter):
  1019. */
  1020. ret = lookup_pi_state(uval, hb, &q);
  1021. if (unlikely(ret)) {
  1022. /*
  1023. * There were no waiters and the owner task lookup
  1024. * failed. When the OWNER_DIED bit is set, then we
  1025. * know that this is a robust futex and we actually
  1026. * take the lock. This is safe as we are protected by
  1027. * the hash bucket lock. We also set the waiters bit
  1028. * unconditionally here, to simplify glibc handling of
  1029. * multiple tasks racing to acquire the lock and
  1030. * cleanup the problems which were left by the dead
  1031. * owner.
  1032. */
  1033. if (curval & FUTEX_OWNER_DIED) {
  1034. uval = newval;
  1035. newval = current->pid |
  1036. FUTEX_OWNER_DIED | FUTEX_WAITERS;
  1037. pagefault_disable();
  1038. curval = futex_atomic_cmpxchg_inatomic(uaddr,
  1039. uval, newval);
  1040. pagefault_enable();
  1041. if (unlikely(curval == -EFAULT))
  1042. goto uaddr_faulted;
  1043. if (unlikely(curval != uval))
  1044. goto retry_locked;
  1045. ret = 0;
  1046. }
  1047. goto out_unlock_release_sem;
  1048. }
  1049. /*
  1050. * Only actually queue now that the atomic ops are done:
  1051. */
  1052. __queue_me(&q, hb);
  1053. /*
  1054. * Now the futex is queued and we have checked the data, we
  1055. * don't want to hold mmap_sem while we sleep.
  1056. */
  1057. up_read(&curr->mm->mmap_sem);
  1058. WARN_ON(!q.pi_state);
  1059. /*
  1060. * Block on the PI mutex:
  1061. */
  1062. if (!trylock)
  1063. ret = rt_mutex_timed_lock(&q.pi_state->pi_mutex, to, 1);
  1064. else {
  1065. ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
  1066. /* Fixup the trylock return value: */
  1067. ret = ret ? 0 : -EWOULDBLOCK;
  1068. }
  1069. down_read(&curr->mm->mmap_sem);
  1070. spin_lock(q.lock_ptr);
  1071. /*
  1072. * Got the lock. We might not be the anticipated owner if we
  1073. * did a lock-steal - fix up the PI-state in that case.
  1074. */
  1075. if (!ret && q.pi_state->owner != curr) {
  1076. u32 newtid = current->pid | FUTEX_WAITERS;
  1077. /* Owner died? */
  1078. if (q.pi_state->owner != NULL) {
  1079. spin_lock_irq(&q.pi_state->owner->pi_lock);
  1080. WARN_ON(list_empty(&q.pi_state->list));
  1081. list_del_init(&q.pi_state->list);
  1082. spin_unlock_irq(&q.pi_state->owner->pi_lock);
  1083. } else
  1084. newtid |= FUTEX_OWNER_DIED;
  1085. q.pi_state->owner = current;
  1086. spin_lock_irq(&current->pi_lock);
  1087. WARN_ON(!list_empty(&q.pi_state->list));
  1088. list_add(&q.pi_state->list, &current->pi_state_list);
  1089. spin_unlock_irq(&current->pi_lock);
  1090. /* Unqueue and drop the lock */
  1091. unqueue_me_pi(&q, hb);
  1092. up_read(&curr->mm->mmap_sem);
  1093. /*
  1094. * We own it, so we have to replace the pending owner
  1095. * TID. This must be atomic as we have preserve the
  1096. * owner died bit here.
  1097. */
  1098. ret = get_user(uval, uaddr);
  1099. while (!ret) {
  1100. newval = (uval & FUTEX_OWNER_DIED) | newtid;
  1101. curval = futex_atomic_cmpxchg_inatomic(uaddr,
  1102. uval, newval);
  1103. if (curval == -EFAULT)
  1104. ret = -EFAULT;
  1105. if (curval == uval)
  1106. break;
  1107. uval = curval;
  1108. }
  1109. } else {
  1110. /*
  1111. * Catch the rare case, where the lock was released
  1112. * when we were on the way back before we locked
  1113. * the hash bucket.
  1114. */
  1115. if (ret && q.pi_state->owner == curr) {
  1116. if (rt_mutex_trylock(&q.pi_state->pi_mutex))
  1117. ret = 0;
  1118. }
  1119. /* Unqueue and drop the lock */
  1120. unqueue_me_pi(&q, hb);
  1121. up_read(&curr->mm->mmap_sem);
  1122. }
  1123. if (!detect && ret == -EDEADLK && 0)
  1124. force_sig(SIGKILL, current);
  1125. return ret != -EINTR ? ret : -ERESTARTNOINTR;
  1126. out_unlock_release_sem:
  1127. queue_unlock(&q, hb);
  1128. out_release_sem:
  1129. up_read(&curr->mm->mmap_sem);
  1130. return ret;
  1131. uaddr_faulted:
  1132. /*
  1133. * We have to r/w *(int __user *)uaddr, but we can't modify it
  1134. * non-atomically. Therefore, if get_user below is not
  1135. * enough, we need to handle the fault ourselves, while
  1136. * still holding the mmap_sem.
  1137. */
  1138. if (attempt++) {
  1139. if (futex_handle_fault((unsigned long)uaddr, attempt)) {
  1140. ret = -EFAULT;
  1141. goto out_unlock_release_sem;
  1142. }
  1143. goto retry_locked;
  1144. }
  1145. queue_unlock(&q, hb);
  1146. up_read(&curr->mm->mmap_sem);
  1147. ret = get_user(uval, uaddr);
  1148. if (!ret && (uval != -EFAULT))
  1149. goto retry;
  1150. return ret;
  1151. }
  1152. /*
  1153. * Userspace attempted a TID -> 0 atomic transition, and failed.
  1154. * This is the in-kernel slowpath: we look up the PI state (if any),
  1155. * and do the rt-mutex unlock.
  1156. */
  1157. static int futex_unlock_pi(u32 __user *uaddr)
  1158. {
  1159. struct futex_hash_bucket *hb;
  1160. struct futex_q *this, *next;
  1161. u32 uval;
  1162. struct list_head *head;
  1163. union futex_key key;
  1164. int ret, attempt = 0;
  1165. retry:
  1166. if (get_user(uval, uaddr))
  1167. return -EFAULT;
  1168. /*
  1169. * We release only a lock we actually own:
  1170. */
  1171. if ((uval & FUTEX_TID_MASK) != current->pid)
  1172. return -EPERM;
  1173. /*
  1174. * First take all the futex related locks:
  1175. */
  1176. down_read(&current->mm->mmap_sem);
  1177. ret = get_futex_key(uaddr, &key);
  1178. if (unlikely(ret != 0))
  1179. goto out;
  1180. hb = hash_futex(&key);
  1181. spin_lock(&hb->lock);
  1182. retry_locked:
  1183. /*
  1184. * To avoid races, try to do the TID -> 0 atomic transition
  1185. * again. If it succeeds then we can return without waking
  1186. * anyone else up:
  1187. */
  1188. if (!(uval & FUTEX_OWNER_DIED)) {
  1189. pagefault_disable();
  1190. uval = futex_atomic_cmpxchg_inatomic(uaddr, current->pid, 0);
  1191. pagefault_enable();
  1192. }
  1193. if (unlikely(uval == -EFAULT))
  1194. goto pi_faulted;
  1195. /*
  1196. * Rare case: we managed to release the lock atomically,
  1197. * no need to wake anyone else up:
  1198. */
  1199. if (unlikely(uval == current->pid))
  1200. goto out_unlock;
  1201. /*
  1202. * Ok, other tasks may need to be woken up - check waiters
  1203. * and do the wakeup if necessary:
  1204. */
  1205. head = &hb->chain;
  1206. list_for_each_entry_safe(this, next, head, list) {
  1207. if (!match_futex (&this->key, &key))
  1208. continue;
  1209. ret = wake_futex_pi(uaddr, uval, this);
  1210. /*
  1211. * The atomic access to the futex value
  1212. * generated a pagefault, so retry the
  1213. * user-access and the wakeup:
  1214. */
  1215. if (ret == -EFAULT)
  1216. goto pi_faulted;
  1217. goto out_unlock;
  1218. }
  1219. /*
  1220. * No waiters - kernel unlocks the futex:
  1221. */
  1222. if (!(uval & FUTEX_OWNER_DIED)) {
  1223. ret = unlock_futex_pi(uaddr, uval);
  1224. if (ret == -EFAULT)
  1225. goto pi_faulted;
  1226. }
  1227. out_unlock:
  1228. spin_unlock(&hb->lock);
  1229. out:
  1230. up_read(&current->mm->mmap_sem);
  1231. return ret;
  1232. pi_faulted:
  1233. /*
  1234. * We have to r/w *(int __user *)uaddr, but we can't modify it
  1235. * non-atomically. Therefore, if get_user below is not
  1236. * enough, we need to handle the fault ourselves, while
  1237. * still holding the mmap_sem.
  1238. */
  1239. if (attempt++) {
  1240. if (futex_handle_fault((unsigned long)uaddr, attempt)) {
  1241. ret = -EFAULT;
  1242. goto out_unlock;
  1243. }
  1244. goto retry_locked;
  1245. }
  1246. spin_unlock(&hb->lock);
  1247. up_read(&current->mm->mmap_sem);
  1248. ret = get_user(uval, uaddr);
  1249. if (!ret && (uval != -EFAULT))
  1250. goto retry;
  1251. return ret;
  1252. }
  1253. static int futex_close(struct inode *inode, struct file *filp)
  1254. {
  1255. struct futex_q *q = filp->private_data;
  1256. unqueue_me(q);
  1257. kfree(q);
  1258. return 0;
  1259. }
  1260. /* This is one-shot: once it's gone off you need a new fd */
  1261. static unsigned int futex_poll(struct file *filp,
  1262. struct poll_table_struct *wait)
  1263. {
  1264. struct futex_q *q = filp->private_data;
  1265. int ret = 0;
  1266. poll_wait(filp, &q->waiters, wait);
  1267. /*
  1268. * list_empty() is safe here without any lock.
  1269. * q->lock_ptr != 0 is not safe, because of ordering against wakeup.
  1270. */
  1271. if (list_empty(&q->list))
  1272. ret = POLLIN | POLLRDNORM;
  1273. return ret;
  1274. }
  1275. static const struct file_operations futex_fops = {
  1276. .release = futex_close,
  1277. .poll = futex_poll,
  1278. };
  1279. /*
  1280. * Signal allows caller to avoid the race which would occur if they
  1281. * set the sigio stuff up afterwards.
  1282. */
  1283. static int futex_fd(u32 __user *uaddr, int signal)
  1284. {
  1285. struct futex_q *q;
  1286. struct file *filp;
  1287. int ret, err;
  1288. static unsigned long printk_interval;
  1289. if (printk_timed_ratelimit(&printk_interval, 60 * 60 * 1000)) {
  1290. printk(KERN_WARNING "Process `%s' used FUTEX_FD, which "
  1291. "will be removed from the kernel in June 2007\n",
  1292. current->comm);
  1293. }
  1294. ret = -EINVAL;
  1295. if (!valid_signal(signal))
  1296. goto out;
  1297. ret = get_unused_fd();
  1298. if (ret < 0)
  1299. goto out;
  1300. filp = get_empty_filp();
  1301. if (!filp) {
  1302. put_unused_fd(ret);
  1303. ret = -ENFILE;
  1304. goto out;
  1305. }
  1306. filp->f_op = &futex_fops;
  1307. filp->f_path.mnt = mntget(futex_mnt);
  1308. filp->f_path.dentry = dget(futex_mnt->mnt_root);
  1309. filp->f_mapping = filp->f_path.dentry->d_inode->i_mapping;
  1310. if (signal) {
  1311. err = __f_setown(filp, task_pid(current), PIDTYPE_PID, 1);
  1312. if (err < 0) {
  1313. goto error;
  1314. }
  1315. filp->f_owner.signum = signal;
  1316. }
  1317. q = kmalloc(sizeof(*q), GFP_KERNEL);
  1318. if (!q) {
  1319. err = -ENOMEM;
  1320. goto error;
  1321. }
  1322. q->pi_state = NULL;
  1323. down_read(&current->mm->mmap_sem);
  1324. err = get_futex_key(uaddr, &q->key);
  1325. if (unlikely(err != 0)) {
  1326. up_read(&current->mm->mmap_sem);
  1327. kfree(q);
  1328. goto error;
  1329. }
  1330. /*
  1331. * queue_me() must be called before releasing mmap_sem, because
  1332. * key->shared.inode needs to be referenced while holding it.
  1333. */
  1334. filp->private_data = q;
  1335. queue_me(q, ret, filp);
  1336. up_read(&current->mm->mmap_sem);
  1337. /* Now we map fd to filp, so userspace can access it */
  1338. fd_install(ret, filp);
  1339. out:
  1340. return ret;
  1341. error:
  1342. put_unused_fd(ret);
  1343. put_filp(filp);
  1344. ret = err;
  1345. goto out;
  1346. }
  1347. /*
  1348. * Support for robust futexes: the kernel cleans up held futexes at
  1349. * thread exit time.
  1350. *
  1351. * Implementation: user-space maintains a per-thread list of locks it
  1352. * is holding. Upon do_exit(), the kernel carefully walks this list,
  1353. * and marks all locks that are owned by this thread with the
  1354. * FUTEX_OWNER_DIED bit, and wakes up a waiter (if any). The list is
  1355. * always manipulated with the lock held, so the list is private and
  1356. * per-thread. Userspace also maintains a per-thread 'list_op_pending'
  1357. * field, to allow the kernel to clean up if the thread dies after
  1358. * acquiring the lock, but just before it could have added itself to
  1359. * the list. There can only be one such pending lock.
  1360. */
  1361. /**
  1362. * sys_set_robust_list - set the robust-futex list head of a task
  1363. * @head: pointer to the list-head
  1364. * @len: length of the list-head, as userspace expects
  1365. */
  1366. asmlinkage long
  1367. sys_set_robust_list(struct robust_list_head __user *head,
  1368. size_t len)
  1369. {
  1370. /*
  1371. * The kernel knows only one size for now:
  1372. */
  1373. if (unlikely(len != sizeof(*head)))
  1374. return -EINVAL;
  1375. current->robust_list = head;
  1376. return 0;
  1377. }
  1378. /**
  1379. * sys_get_robust_list - get the robust-futex list head of a task
  1380. * @pid: pid of the process [zero for current task]
  1381. * @head_ptr: pointer to a list-head pointer, the kernel fills it in
  1382. * @len_ptr: pointer to a length field, the kernel fills in the header size
  1383. */
  1384. asmlinkage long
  1385. sys_get_robust_list(int pid, struct robust_list_head __user * __user *head_ptr,
  1386. size_t __user *len_ptr)
  1387. {
  1388. struct robust_list_head __user *head;
  1389. unsigned long ret;
  1390. if (!pid)
  1391. head = current->robust_list;
  1392. else {
  1393. struct task_struct *p;
  1394. ret = -ESRCH;
  1395. rcu_read_lock();
  1396. p = find_task_by_pid(pid);
  1397. if (!p)
  1398. goto err_unlock;
  1399. ret = -EPERM;
  1400. if ((current->euid != p->euid) && (current->euid != p->uid) &&
  1401. !capable(CAP_SYS_PTRACE))
  1402. goto err_unlock;
  1403. head = p->robust_list;
  1404. rcu_read_unlock();
  1405. }
  1406. if (put_user(sizeof(*head), len_ptr))
  1407. return -EFAULT;
  1408. return put_user(head, head_ptr);
  1409. err_unlock:
  1410. rcu_read_unlock();
  1411. return ret;
  1412. }
  1413. /*
  1414. * Process a futex-list entry, check whether it's owned by the
  1415. * dying task, and do notification if so:
  1416. */
  1417. int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
  1418. {
  1419. u32 uval, nval, mval;
  1420. retry:
  1421. if (get_user(uval, uaddr))
  1422. return -1;
  1423. if ((uval & FUTEX_TID_MASK) == curr->pid) {
  1424. /*
  1425. * Ok, this dying thread is truly holding a futex
  1426. * of interest. Set the OWNER_DIED bit atomically
  1427. * via cmpxchg, and if the value had FUTEX_WAITERS
  1428. * set, wake up a waiter (if any). (We have to do a
  1429. * futex_wake() even if OWNER_DIED is already set -
  1430. * to handle the rare but possible case of recursive
  1431. * thread-death.) The rest of the cleanup is done in
  1432. * userspace.
  1433. */
  1434. mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
  1435. nval = futex_atomic_cmpxchg_inatomic(uaddr, uval, mval);
  1436. if (nval == -EFAULT)
  1437. return -1;
  1438. if (nval != uval)
  1439. goto retry;
  1440. /*
  1441. * Wake robust non-PI futexes here. The wakeup of
  1442. * PI futexes happens in exit_pi_state():
  1443. */
  1444. if (!pi) {
  1445. if (uval & FUTEX_WAITERS)
  1446. futex_wake(uaddr, 1);
  1447. }
  1448. }
  1449. return 0;
  1450. }
  1451. /*
  1452. * Fetch a robust-list pointer. Bit 0 signals PI futexes:
  1453. */
  1454. static inline int fetch_robust_entry(struct robust_list __user **entry,
  1455. struct robust_list __user * __user *head,
  1456. int *pi)
  1457. {
  1458. unsigned long uentry;
  1459. if (get_user(uentry, (unsigned long __user *)head))
  1460. return -EFAULT;
  1461. *entry = (void __user *)(uentry & ~1UL);
  1462. *pi = uentry & 1;
  1463. return 0;
  1464. }
  1465. /*
  1466. * Walk curr->robust_list (very carefully, it's a userspace list!)
  1467. * and mark any locks found there dead, and notify any waiters.
  1468. *
  1469. * We silently return on any sign of list-walking problem.
  1470. */
  1471. void exit_robust_list(struct task_struct *curr)
  1472. {
  1473. struct robust_list_head __user *head = curr->robust_list;
  1474. struct robust_list __user *entry, *pending;
  1475. unsigned int limit = ROBUST_LIST_LIMIT, pi, pip;
  1476. unsigned long futex_offset;
  1477. /*
  1478. * Fetch the list head (which was registered earlier, via
  1479. * sys_set_robust_list()):
  1480. */
  1481. if (fetch_robust_entry(&entry, &head->list.next, &pi))
  1482. return;
  1483. /*
  1484. * Fetch the relative futex offset:
  1485. */
  1486. if (get_user(futex_offset, &head->futex_offset))
  1487. return;
  1488. /*
  1489. * Fetch any possibly pending lock-add first, and handle it
  1490. * if it exists:
  1491. */
  1492. if (fetch_robust_entry(&pending, &head->list_op_pending, &pip))
  1493. return;
  1494. if (pending)
  1495. handle_futex_death((void __user *)pending + futex_offset, curr, pip);
  1496. while (entry != &head->list) {
  1497. /*
  1498. * A pending lock might already be on the list, so
  1499. * don't process it twice:
  1500. */
  1501. if (entry != pending)
  1502. if (handle_futex_death((void __user *)entry + futex_offset,
  1503. curr, pi))
  1504. return;
  1505. /*
  1506. * Fetch the next entry in the list:
  1507. */
  1508. if (fetch_robust_entry(&entry, &entry->next, &pi))
  1509. return;
  1510. /*
  1511. * Avoid excessively long or circular lists:
  1512. */
  1513. if (!--limit)
  1514. break;
  1515. cond_resched();
  1516. }
  1517. }
  1518. long do_futex(u32 __user *uaddr, int op, u32 val, unsigned long timeout,
  1519. u32 __user *uaddr2, u32 val2, u32 val3)
  1520. {
  1521. int ret;
  1522. switch (op) {
  1523. case FUTEX_WAIT:
  1524. ret = futex_wait(uaddr, val, timeout);
  1525. break;
  1526. case FUTEX_WAKE:
  1527. ret = futex_wake(uaddr, val);
  1528. break;
  1529. case FUTEX_FD:
  1530. /* non-zero val means F_SETOWN(getpid()) & F_SETSIG(val) */
  1531. ret = futex_fd(uaddr, val);
  1532. break;
  1533. case FUTEX_REQUEUE:
  1534. ret = futex_requeue(uaddr, uaddr2, val, val2, NULL);
  1535. break;
  1536. case FUTEX_CMP_REQUEUE:
  1537. ret = futex_requeue(uaddr, uaddr2, val, val2, &val3);
  1538. break;
  1539. case FUTEX_WAKE_OP:
  1540. ret = futex_wake_op(uaddr, uaddr2, val, val2, val3);
  1541. break;
  1542. case FUTEX_LOCK_PI:
  1543. ret = futex_lock_pi(uaddr, val, timeout, val2, 0);
  1544. break;
  1545. case FUTEX_UNLOCK_PI:
  1546. ret = futex_unlock_pi(uaddr);
  1547. break;
  1548. case FUTEX_TRYLOCK_PI:
  1549. ret = futex_lock_pi(uaddr, 0, timeout, val2, 1);
  1550. break;
  1551. default:
  1552. ret = -ENOSYS;
  1553. }
  1554. return ret;
  1555. }
  1556. asmlinkage long sys_futex(u32 __user *uaddr, int op, u32 val,
  1557. struct timespec __user *utime, u32 __user *uaddr2,
  1558. u32 val3)
  1559. {
  1560. struct timespec t;
  1561. unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
  1562. u32 val2 = 0;
  1563. if (utime && (op == FUTEX_WAIT || op == FUTEX_LOCK_PI)) {
  1564. if (copy_from_user(&t, utime, sizeof(t)) != 0)
  1565. return -EFAULT;
  1566. if (!timespec_valid(&t))
  1567. return -EINVAL;
  1568. if (op == FUTEX_WAIT)
  1569. timeout = timespec_to_jiffies(&t) + 1;
  1570. else {
  1571. timeout = t.tv_sec;
  1572. val2 = t.tv_nsec;
  1573. }
  1574. }
  1575. /*
  1576. * requeue parameter in 'utime' if op == FUTEX_REQUEUE.
  1577. */
  1578. if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE)
  1579. val2 = (u32) (unsigned long) utime;
  1580. return do_futex(uaddr, op, val, timeout, uaddr2, val2, val3);
  1581. }
  1582. static int futexfs_get_sb(struct file_system_type *fs_type,
  1583. int flags, const char *dev_name, void *data,
  1584. struct vfsmount *mnt)
  1585. {
  1586. return get_sb_pseudo(fs_type, "futex", NULL, 0xBAD1DEA, mnt);
  1587. }
  1588. static struct file_system_type futex_fs_type = {
  1589. .name = "futexfs",
  1590. .get_sb = futexfs_get_sb,
  1591. .kill_sb = kill_anon_super,
  1592. };
  1593. static int __init init(void)
  1594. {
  1595. int i = register_filesystem(&futex_fs_type);
  1596. if (i)
  1597. return i;
  1598. futex_mnt = kern_mount(&futex_fs_type);
  1599. if (IS_ERR(futex_mnt)) {
  1600. unregister_filesystem(&futex_fs_type);
  1601. return PTR_ERR(futex_mnt);
  1602. }
  1603. for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
  1604. INIT_LIST_HEAD(&futex_queues[i].chain);
  1605. spin_lock_init(&futex_queues[i].lock);
  1606. }
  1607. return 0;
  1608. }
  1609. __initcall(init);